Mange elever blir forvirret mens de forstår begrepet tidskompleksitet, men i denne artikkelen vil vi forklare det med et veldig enkelt eksempel.
Sp. Tenk deg et klasserom med 100 elever der du ga pennen til én person. Du må finne den pennen uten å vite hvem du ga den til.
Her er noen måter å finne pennen og hva O-ordren er.
- På 2 ): Du går og spør den første personen i klassen om han har pennen. Du spør også denne personen om de andre 99 personene i klasserommet om de har den pennen og så videre,
Dette er det vi kaller O(n2). - På): Å gå og spørre hver elev individuelt er O(N).
- O(log n): Nå deler jeg klassen i to grupper, og spør så: Er det på venstre side, eller høyre side av klasserommet? Så tar jeg den gruppen og deler den i to og spør igjen, og så videre. Gjenta prosessen til du sitter igjen med en elev som har pennen din. Dette er hva du mener med O(log n).
Jeg må kanskje gjøre:
- De På 2 ) søker hvis bare én elev vet på hvilken elev pennen er skjult .
- De På) hvis en elev hadde pennen og bare de visste det .
- De O(log n) søk hvis alle elevene visste , men ville bare fortelle meg hvis jeg gjettet riktig side.
Ovennevnte O -> kalles Stort – Oh som er en asymptotisk notasjon. Det finnes andre asymptotiske notasjoner som theta og Omega .
MERK: Vi er interessert i veksttakten over tid med hensyn til innspillene som ble tatt under programgjennomføringen.
Er tidskompleksiteten til en algoritme/kode den samme som kjøre-/utførelsestidspunktet for koden?
Tidskompleksiteten til en algoritme/kode er ikke lik den faktiske tiden som kreves for å utføre en bestemt kode, men antall ganger en setning kjøres. Vi kan bevise dette ved å bruke tidskommando .
For eksempel: Skriv kode i C/C++ eller et hvilket som helst annet språk for å finne maksimum mellom N tall, der N varierer fra 10, 100, 1000 og 10000. For Linux-basert operativsystem (Fedora eller Ubuntu), bruk kommandoene nedenfor:
java null sjekk
For å kompilere programmet: gcc program.c – o program
For å kjøre programmet: tid ./program
Du vil få overraskende resultater, dvs.:
- For N = 10: du kan få 0,5 ms tid,
- For N = 10 000: du kan få 0,2 ms tid.
- Du vil også få forskjellige tidspunkter på forskjellige maskiner. Selv om du ikke får de samme tidspunktene på samme maskin for samme kode, er årsaken bak det gjeldende nettverksbelastningen.
Så vi kan si at faktisk tid som kreves for å utføre kode er maskinavhengig (enten du bruker Pentium 1 eller Pentium 5), og det vurderer også nettverksbelastningen hvis maskinen din er i LAN/WAN.
Hva menes med tidskompleksiteten til en algoritme?
Nå oppstår spørsmålet om tidskompleksitet ikke er den faktiske tiden som kreves for å utføre koden, hva er det da?
Svaret er:
I stedet for å måle den faktiske tiden som kreves for å utføre hver setning i koden, Tidskompleksitet vurderer hvor mange ganger hver setning utføres.
Eksempel 1: Tenk på den enkle koden nedenfor skriv ut Hei verden
edith mack hirschC++
#include using namespace std; int main() { cout << 'Hello World'; return 0; } // This code is contributed by vikash36905.> C #include int main() { printf('Hello World'); return 0; }> Java import java.io.*; class GFG { public static void main(String[] args) { System.out.print('Hello World'); } } // This code is contributed by vikash36905.> Python3 print('Hello World') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code Console.WriteLine('Hello World'); } } // This code is contributed by lokesh> Javascript console.log('Hello World') // This code is contributed by nilha72xi.> Produksjon
Hello World>
Tidskompleksitet: I koden ovenfor skrives Hello World bare ut én gang på skjermen.
Så tidskompleksiteten er konstant: O(1) dvs. hver gang det kreves en konstant mengde tid for å utføre kode, uansett hvilket operativsystem eller hvilke maskinkonfigurasjoner du bruker.
Auxiliary Space : O(1)
Eksempel 2:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i++) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by vikash36905.> C #include void main() { int i, n = 8; for (i = 1; i <= n; i++) { printf('Hello World !!!
'); } }> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { System.out.printf('Hello World !!!
'); } } } // This code is contributed by Rajput-Ji> Python3 # Python code n = 8 for i in range(1, n + 1): print('Hello World !!!') # This code is contributed by lokesh> C# using System; public class GFG { public static void Main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { Console.Write('Hello World !!!
'); } } } // This code contributed by Rajput-Ji> Javascript let i, n = 8; for (i = 1; i <= n; i++) { console.log('Hello World !!!'); }> Produksjon
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Tidskompleksitet: I koden ovenfor Hello World !!! skrives kun ut n ganger på skjermen, da verdien av n kan endres.
Så tidskompleksiteten er lineær: O(n) dvs. hver gang kreves det en lineær tid for å utføre kode.
Hjelpeplass: O(1)
Eksempel 3:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include void main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i=i*2) { System.out.println('Hello World !!!'); } } } // This code is contributed by Suruchi Kumari> Python3 n = 8 # for (i = 1; i <= n; i=i*2) { for i in range(1, n+1, 2): print('Hello World !!!') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code int i, n = 8; for (i = 1; i <= n; i=i*2) { Console.Write('Hello World !!!
'); } } } // This code is contributed by lokeshmvs21.> Javascript for (i = 1; i <= 8; i=i*2) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Produksjon
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Tidskompleksitet: O(log2(n))
Hjelpeplass: O(1)
Eksempel 4:
C++ #include #include using namespace std; int main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include #include void main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java import java.lang.Math; class GFG { public static void main(String args[]){ int i, n = 8; for (i = 2; i <= n; i=(int)Math.pow(i,2)) { System.out.println('Hello World !!!'); } } }> Python3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # Denne koden er bidratt av akashish__> C# using System; using System.Collections.Generic; public class GFG { static public void Main() { int i, n = 8; for (i = 2; i <= n; i = (int)Math.Pow(i, 2)) { Console.WriteLine('Hello World !!!'); } } } // This code is contributed by akashish__> Javascript for (let i = 2; i <= 8; i=Math.pow(i,2)) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Produksjon
Hello World !!! Hello World !!!>
Tidskompleksitet: O(log(log n))
Hjelpeplass: O(1)
Hvordan finne tidskompleksiteten til en algoritme?
La oss nå se noen andre eksempler og prosessen for å finne tidskompleksiteten til en algoritme:
Eksempel: La oss vurdere en modellmaskin som har følgende spesifikasjoner:
- Enkel prosessor
- 32 bit
- Sekvensiell utførelse
- 1 tidsenhet for aritmetiske og logiske operasjoner
- 1 enhetstid for oppdrag og returoppgaver
Q1. Finn summen av 2 tall på maskinen ovenfor:
For enhver maskin vil pseudokoden for å legge til to tall være omtrent slik:
C++ // Pseudocode : Sum(a, b) { return a + b } #include using namespace std; int sum(int a,int b) { return a+b; } int main() { int a = 5, b = 6; cout< C Pseudocode : Sum(a, b) { return a + b }> Java // Pseudocode : Sum(a, b) { return a + b } import java.io.*; class GFG { public static int sum(int a, int b) { return a + b; } public static void main(String[] args) { int a = 5, b = 6; System.out.println(sum(a, b)); } } // This code is contributed by akashish__> Python3 # Pseudocode : Sum(a, b) { return a + b } a = 5 b = 6 def sum(a,b): return a+b # function call print(sum(a,b))> C# // Pseudocode : Sum(a, b) { return a + b } using System; public class GFG { public static int sum(int a, int b) { return a + b; } static public void Main() { int a = 5, b = 6; Console.WriteLine(sum(a, b)); } } // This code is contributed by akashish__> Javascript // Pseudocode : Sum(a, b) { return a + b } function sum(a, b) { return a + b; } let a = 5, b = 6; console.log(sum(a, b)); // This code is contributed by akashish__> Produksjon
11>
Tidskompleksitet:
- Koden ovenfor vil ta 2 tidsenheter (konstant):
- en for aritmetiske operasjoner og
- en for retur. (i henhold til konvensjonene ovenfor).
- Derfor totalkostnad for å utføre sumoperasjon ( ) = 1 + 1 = 2
- Tidskompleksitet = O(2) = O(1) , siden 2 er konstant
Hjelpeplass: O(1)
Q2. Finn summen av alle elementene i en liste/matrise
Pseudokoden for å gjøre det kan gis som:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->matrise og // n->antall elementer i matrise { int sum = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } int main() { int A[] = { 5, 6, 1, 2 }; int n = sizeof(A) / sizeof(A[0]); cout << list_Sum(A, n); return 0; } // This code is contributed by akashish__> C Pseudocode : list_Sum(A, n) // A->array og // n->antall elementer i array { sum = 0 for i = 0 til n-1 sum = sum + A[i] return sum }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->matrise og // n->antall elementer i matrise { int sum = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } public static void main(String[] args) { int[] A = { 5, 6, 1, 2 }; int n = A.length; System.out.println(list_Sum(A, n)); } } // This code is contributed by lokeshmvs21.> Python3 # A function to calculate the sum of the elements in an array def list_sum(A, n): sum = 0 for i in range(n): sum += A[i] return sum # A sample array A = [5, 6, 1, 2] # Finding the number of elements in the array n = len(A) # Call the function and print the result print(list_sum(A, n))>
C# using System; public class GFG { public static int list_Sum(int[] A, int n) // A->matrise og // n->antall elementer i matrise { int sum = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } static public void Main() { int[] A = { 5, 6, 1, 2 }; int n = A.Length; Console.WriteLine(list_Sum(A, n)); } } // This code is contributed by akashish__> Javascript function list_Sum(A, n) // A->matrise og // n->antall elementer i matrise { la sum = 0; for (la i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } let A = [ 5, 6, 1, 2 ]; let n = A.length; console.log(list_Sum(A, n)); // This code is contributed by akashish__> Produksjon
14>
For å forstå tidskompleksiteten til koden ovenfor, la oss se hvor mye tid hver setning vil ta:
int list_Sum(int A[], int n) { int sum = 0; // cost=1 no of times=1 for(int i=0; i C Pseudocode : list_Sum(A, n) { total =0 // cost=1 no of times=1 for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end false condition) sum = sum + A[i] // cost=2 no of times=n return sum // cost=1 no of times=1 }> Java public class ListSum { // Function to calculate the sum of elements in an array static int listSum(int[] A, int n) { int sum = 0; // Cost = 1, executed 1 time for (int i = 0; i < n; i++) { // Cost = 2, executed n+1 times (+1 for // the end false condition) sum = sum + A[i]; // Cost = 2, executed n times } return sum; // Cost = 1, executed 1 time } // Main method for testing public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5}; int length = array.length; int result = listSum(array, length); System.out.println('Sum: ' + result); } }> Python3 def list_sum(A): sum = 0 for i in range(len(A)): sum = sum + A[i] return sum>
C# using System; class Program { // Function to calculate the sum of elements in a list static int ListSum(int[] A) { int sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (int i = 0; i < A.Length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Driver code static void Main() { // Example usage int[] array = { 1, 2, 3, 4, 5 }; int result = ListSum(array); Console.WriteLine(result); } }> Javascript function listSum(A) { let sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (let i = 0; i < A.length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Example usage let array = [1, 2, 3, 4, 5]; let result = listSum(array); console.log(result);> Derfor den totale kostnaden for å utføre sumoperasjon
Sum=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Derfor er tidskompleksiteten til koden ovenfor På)
Q3. Finn summen av alle elementene i en matrise
For denne er kompleksiteten en polynomligning (kvadratligning for en kvadratisk matrise)
rihanna alder
- Matrise av størrelse n*n => Tsum = a.n 2 + b.n + c
- Siden Tsum er i rekkefølgen n2, derfor Tidskompleksitet = O(n 2 )
#include using namespace std; int main() { int n = 3; int m = 3; int arr[][3] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } cout << sum << endl; return 0; } // contributed by akashish__> Java /*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { int n = 3; int m = 3; int arr[][] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } System.out.println(sum); } } // akashish__> Python3 n = 3 m = 3 arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]] sum = 0 # Iterating over all 1-D arrays in 2-D array for i in range(n): # Printing all elements in ith 1-D array for j in range(m): # Printing jth element of ith row sum += arr[i][j] print(sum) # This code id contributed by shivhack999>
C# using System; class MainClass { static void Main(string[] args) { int n = 3; int m = 3; int[, ] arr = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i, j]; } } Console.WriteLine(sum); } }> Javascript let n = 3; let m = 3; let arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]; let sum = 0; // Iterating over all 1-D arrays in 2-D array for (let i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (let j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } console.log(sum);> Produksjon
43>
Tidskompleksitet: På M)
Programmet itererer gjennom alle elementene i 2D-matrisen ved å bruke to nestede løkker. Den ytre sløyfen itererer n ganger og den indre sløyfen itererer m ganger for hver iterasjon av den ytre sløyfen. Derfor er tidskompleksiteten til programmet O(n*m).
Hjelpeplass: På M)
Programmet bruker en fast mengde hjelpeplass for å lagre 2D-matrisen og noen få heltallsvariabler. Plassen som kreves for 2D-matrisen er nm heltall. Programmet bruker også en enkelt heltallsvariabel for å lagre summen av elementene. Derfor er hjelperomskompleksiteten til programmet O(nm + 1), noe som forenkler til O(n*m).
Avslutningsvis er tidskompleksiteten til programmet O(nm), og hjelperomskompleksiteten er også O(nm).
Så fra eksemplene ovenfor kan vi konkludere med at tiden for utførelse øker med typen operasjoner vi gjør ved å bruke inngangene.
Hvordan sammenligne algoritmer?
For å sammenligne algoritmer, la oss definere noen objektive mål:
- Utførelsestider: Ikke et godt mål da utførelsestiden er spesifikk for en bestemt datamaskin.
- Antall utførte uttalelser: Ikke et godt mål, siden antall utsagn varierer med programmeringsspråket samt stilen til den enkelte programmereren.
- Ideell løsning: La oss anta at vi uttrykker kjøretiden til en gitt algoritme som en funksjon av inngangsstørrelsen n (dvs. f(n)) og sammenligner disse forskjellige funksjonene tilsvarende kjøretider. Denne typen sammenligning er uavhengig av maskintid, programmeringsstil osv.
Derfor kan en ideell løsning brukes til å sammenligne algoritmer.
Relaterte artikler:
- Tidskompleksitet og romkompleksitet
- Analyse av algoritmer | Sett 1 (asymptotisk analyse)
- Analyse av algoritmer | Sett 2 (dårligste, gjennomsnittlige og beste tilfeller)
- Analyse av algoritmer | Sett 3 (asymptotiske notasjoner)
- Analyse av algoritmer | Sett 4 (Analyse av løkker)
- Analyse av algoritme | Sett 5 (introduksjon til amortisert analyse)
- Diverse problemer med tidskompleksitet
- Praksisspørsmål om tidskompleksitetsanalyse
- Kjenne til kompleksiteten i konkurrerende programmering