Mange elever bliver forvirrede, mens de forstår begrebet tidskompleksitet, men i denne artikel vil vi forklare det med et meget simpelt eksempel.
Q. Forestil dig et klasseværelse med 100 elever, hvor du gav din pen til én person. Du skal finde den pen uden at vide, hvem du gav den til.
Her er nogle måder at finde pennen på, og hvad O-rækkefølgen er.
- På 2 ): Du går hen og spørger den første i klassen, om han har pennen. Du spørger også denne person om de andre 99 personer i klasseværelset, om de har den pen og så videre,
Det er det, vi kalder O(n2). - På): At gå og spørge hver elev individuelt er O(N).
- O(log n): Nu deler jeg klassen op i to grupper, og spørger så: Er det i venstre side eller i højre side af klasseværelset? Så tager jeg den gruppe og deler den i to og spørger igen, og så videre. Gentag processen, indtil du står tilbage med en elev, der har din pen. Dette er hvad du mener med O(log n).
Jeg skal muligvis gøre:
- Det På 2 ) søger hvis kun én elev ved, hvilken elev pennen er gemt på .
- Det På) hvis en elev havde pennen, og kun de vidste den .
- Det O(log n) søg hvis vidste alle elever , men ville kun fortælle mig, hvis jeg gættede den rigtige side.
Ovenstående O -> kaldes Stort – Åh hvilket er en asymptotisk notation. Der er andre asymptotiske notationer synes godt om theta og Omega .
BEMÆRK: Vi er interesserede i vækstraten over tid i forhold til de input, der er taget under programgennemførelsen.
Er tidskompleksiteten af en algoritme/kode den samme som den kørende/udførelsestidspunkt for koden?
Tidskompleksiteten af en algoritme/kode er ikke lig med den faktiske tid, der kræves for at udføre en bestemt kode, men antallet af gange, en sætning udføres. Vi kan bevise dette ved at bruge tidskommando .
For eksempel: Skriv kode i C/C++ eller et hvilket som helst andet sprog for at finde maksimum mellem N tal, hvor N varierer fra 10, 100, 1000 og 10000. For Linux-baseret operativsystem (Fedora eller Ubuntu), brug nedenstående kommandoer:
mylivecriclet
For at kompilere programmet: gcc program.c – o program
For at udfø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å forskellige timings på forskellige maskiner. Selvom du ikke får de samme timings på den samme maskine for den samme kode, er årsagen bag det den aktuelle netværksbelastning.
Så vi kan sige, at den faktiske tid, der kræves for at udføre kode, er maskinafhængig (uanset om du bruger Pentium 1 eller Pentium 5), og det tager også hensyn til netværksbelastningen, hvis din maskine er i LAN/WAN.
Hvad menes med en algoritmes tidskompleksitet?
Nu opstår spørgsmålet, hvis tidskompleksitet ikke er den faktiske tid, der kræves for at udføre koden, hvad er det så?
Svaret er:
I stedet for at måle den faktiske tid, der kræves til at udføre hver sætning i koden, Tidskompleksitet overvejer, hvor mange gange hver sætning udføres.
Eksempel 1: Overvej nedenstående enkle kode til print Hej verden
tilfældig ikke i javaC++
#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.> Produktion
Hello World>
Tidskompleksitet: I ovenstående kode udskrives Hello World kun én gang på skærmen.
Så tidskompleksiteten er konstant: O(1) dvs. hver gang, der kræves en konstant mængde tid til at udføre kode, uanset hvilket operativsystem eller hvilken maskinkonfiguration du bruger.
Hjælpeplads : 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 !!!'); }> Produktion
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Tidskompleksitet: I ovenstående kode Hello World !!! udskrives kun n gange på skærmen, da værdien af n kan ændre sig.
Så tidskompleksiteten er lineær: O(n) dvs. hver gang, der kræves en lineær mængde tid for at udføre kode.
Hjælpeplads: 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.> Produktion
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Tidskompleksitet: O(log2(n))
Hjælpeplads: 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 kode er bidraget af 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.> Produktion
Hello World !!! Hello World !!!>
Tidskompleksitet: O(log(log n))
Hjælpeplads: O(1)
Hvordan finder man tidskompleksiteten af en algoritme?
Lad os nu se nogle andre eksempler og processen for at finde tidskompleksiteten af en algoritme:
Eksempel: Lad os overveje en modelmaskine, der har følgende specifikationer:
- Enkelt processor
- 32 bit
- Sekventiel udførelse
- 1 tidsenhed til aritmetiske og logiske operationer
- 1 enhedstid til opgave- og returopgørelser
Q1. Find summen af 2 tal på ovenstående maskine:
For enhver maskine vil pseudokoden for at tilføje to tal være sådan her:
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__> Produktion
11>
Tidskompleksitet:
- Ovenstående kode vil tage 2 tidsenheder (konstant):
- en til aritmetiske operationer og
- en til returnering. (i henhold til ovenstående konventioner).
- Derfor samlede omkostninger til at udføre sum operation ( ) = 1 + 1 = 2
- Tidskompleksitet = O(2) = O(1) , da 2 er konstant
Hjælpeplads: O(1)
Q2. Find summen af alle elementer i en liste/array
Pseudokoden til at gøre det kan gives som:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->matrix og // n->antal elementer i matrix { 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->matrix og // n->antal elementer i matrix { sum = 0 for i = 0 til n-1 sum = sum + A[i] returner sum }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->matrix og // n->antal elementer i matrix { 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->matrix og // n->antal elementer i matrix { 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->matrix og // n->antal elementer i matrix { lad sum = 0; for (lad 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__> Produktion
14>
For at forstå tidskompleksiteten af ovenstående kode, lad os se, hvor meget tid hver erklæring vil tage:
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 de samlede omkostninger til at udføre sum operation
Sum=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Derfor er tidskompleksiteten af ovenstående kode På)
Q3. Find summen af alle elementer i en matrix
For denne er kompleksiteten en polynomialligning (kvadratligning for en kvadratisk matrix)
indstillingsmenu for Android
- Matrix af størrelse n*n => Tsum = a.n 2 + b.n + c
- Da Tsum er i rækkefølgen af 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);> Produktion
43>
Tidskompleksitet: O(n*m)
Programmet itererer gennem alle elementerne i 2D-arrayet ved hjælp af to indlejrede sløjfer. Den ydre løkke itererer n gange, og den indre løkke itererer m gange for hver iteration af den ydre løkke. Derfor er programmets tidskompleksitet O(n*m).
Hjælpeplads: O(n*m)
Programmet bruger en fast mængde hjælpeplads til at gemme 2D-arrayet og nogle få heltalsvariabler. Den nødvendige plads til 2D-arrayet er nm heltal. Programmet bruger også en enkelt heltalsvariabel til at gemme summen af elementerne. Derfor er programmets hjælperumskompleksitet O(nm + 1), hvilket forenkler til O(n*m).
Afslutningsvis er programmets tidskompleksitet O(nm), og hjælperummets kompleksitet er også O(nm).
Så ud fra ovenstående eksempler kan vi konkludere, at udførelsestiden stiger med den type operationer, vi foretager ved hjælp af inputs.
Hvordan sammenligner man algoritmer?
For at sammenligne algoritmer, lad os definere et par objektive mål:
- Udførelsestider: Ikke et godt mål, da udførelsestiderne er specifikke for en bestemt computer.
- Antallet af udførte udsagn: Ikke et godt mål, da antallet af udsagn varierer med programmeringssproget samt stilen på den enkelte programmør.
- Ideel løsning: Lad os antage, at vi udtrykker køretiden for en given algoritme som en funktion af inputstørrelsen n (dvs. f(n)) og sammenligner disse forskellige funktioner svarende til køretider. Denne form for sammenligning er uafhængig af maskintid, programmeringsstil osv.
Derfor kan en ideel løsning bruges til at sammenligne algoritmer.
Relaterede artikler:
- Tidskompleksitet og rumkompleksitet
- Analyse af algoritmer | Sæt 1 (asymptotisk analyse)
- Analyse af algoritmer | Sæt 2 (værste, gennemsnitlige og bedste tilfælde)
- Analyse af algoritmer | Sæt 3 (asymptotiske notationer)
- Analyse af algoritmer | Sæt 4 (Analyse af sløjfer)
- Analyse af algoritme | Sæt 5 (Introduktion til amortiseret analyse)
- Diverse problemer med tidskompleksitet
- Praksisspørgsmål om tidskompleksitetsanalyse
- At kende kompleksiteten i konkurrencedygtig programmering