Många elever blir förvirrade när de förstår begreppet tidskomplexitet, men i den här artikeln kommer vi att förklara det med ett mycket enkelt exempel.
F. Föreställ dig ett klassrum med 100 elever där du gav din penna till en person. Du måste hitta den pennan utan att veta vem du gav den till.
Här är några sätt att hitta pennan och vad O-ordningen är.
- På 2 ): Du går och frågar den första personen i klassen om han har pennan. Dessutom frågar du den här personen om de andra 99 personerna i klassrummet om de har den pennan och så vidare,
Detta är vad vi kallar O(n2). - På): Att gå och fråga varje elev individuellt är O(N).
- O(log n): Nu delar jag upp klassen i två grupper och frågar sedan: Är det på vänster sida, eller höger sida av klassrummet? Sedan tar jag den gruppen och delar upp den i två och frågar igen osv. Upprepa processen tills du är kvar med en elev som har din penna. Detta är vad du menar med O(log n).
Jag kanske behöver göra:
- De På 2 ) söker om endast en elev vet på vilken elev pennan är gömd .
- De På) om en elev hade pennan och bara de visste den .
- De O(log n) sök om alla elever visste , men skulle bara berätta för mig om jag gissade på rätt sida.
Ovanstående O -> kallas Stort – Åh vilket är en asymptotisk notation. Det finns andra asymptotiska notationer tycka om theta och Omega .
NOTERA: Vi är intresserade av tillväxttakten över tid med avseende på de insatser som togs under programmets genomförande.
Är tidskomplexiteten för en algoritm/kod densamma som kör-/exekveringstiden för koden?
Tidskomplexiteten för en algoritm/kod är inte lika med den faktiska tiden som krävs för att exekvera en viss kod, men antalet gånger en programsats exekveras. Vi kan bevisa detta genom att använda tidskommando .
Till exempel: Skriv kod i C/C++ eller något annat språk för att hitta maxvärdet mellan N tal, där N varierar från 10, 100, 1000 och 10000. För Linux-baserat operativsystem (Fedora eller Ubuntu), använd följande kommandon:
typ i java
Så här kompilerar du programmet: gcc program.c – o program
För att köra programmet: tid ./program
Du kommer att få överraskande resultat, dvs.
- För N = 10: du kan få 0,5 ms tid,
- För N = 10 000: du kan få 0,2 ms tid.
- Du kommer också att få olika tider på olika maskiner. Även om du inte kommer att få samma tider på samma maskin för samma kod, är orsaken bakom det den aktuella nätverksbelastningen.
Så vi kan säga att Den faktiska tiden som krävs för att exekvera koden är maskinberoende (oavsett om du använder Pentium 1 eller Pentium 5) och även det tar hänsyn till nätverksbelastningen om din maskin är i LAN/WAN.
Vad menas med tidskomplexiteten hos en algoritm?
Nu uppstår frågan om tidskomplexitet inte är den faktiska tid som krävs för att exekvera koden, vad är det då?
Svaret är:
Istället för att mäta den faktiska tiden som krävs för att exekvera varje sats i koden, Tidskomplexitet tar hänsyn till hur många gånger varje påstående körs.
Exempel 1: Överväg nedanstående enkla kod till print Hej världen
C++ #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>
Tidskomplexitet: I ovanstående kod skrivs Hello World endast ut en gång på skärmen.
Så, tidskomplexiteten är konstant: O(1) det vill säga varje gång det krävs en konstant tid för att exekvera kod, oavsett vilket operativsystem eller vilka maskinkonfigurationer du använder.
Hjälputrymme : O(1)
Exempel 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 !!!>
Tidskomplexitet: I ovanstående kod Hello World !!! skrivs endast ut n gånger på skärmen, eftersom värdet på n kan ändras.
Så, tidskomplexiteten är linjär: O(n) d.v.s. varje gång krävs en linjär tid för att exekvera kod.
Hjälputrymme: O(1)
Exempel 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 !!!>
Tidskomplexitet: O(log2(n))
Hjälputrymme: O(1)
Exempel 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 # Denna kod är bidragit 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.> Produktion
Hello World !!! Hello World !!!>
Tidskomplexitet: O(log(log n))
Hjälputrymme: O(1)
Hur hittar man tidskomplexiteten för en algoritm?
Låt oss nu se några andra exempel och processen för att hitta tidskomplexiteten för en algoritm:
Exempel: Låt oss överväga en modellmaskin som har följande specifikationer:
- Enkel processor
- 32 bitar
- Sekventiell exekvering
- 1 tidsenhet för aritmetiska och logiska operationer
- 1 enhetstid för uppdrag och returutlåtanden
Q1. Hitta summan av 2 siffror på maskinen ovan:
alfabet till siffror
För vilken maskin som helst kommer pseudokoden för att lägga till två siffror vara ungefär så här:
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>
Tidskomplexitet:
- Ovanstående kod kommer att ta 2 tidsenheter (konstant):
- en för aritmetiska operationer och
- en för retur. (enligt ovanstående konventioner).
- Därför totalkostnad för att utföra summaoperation ( ) = 1 + 1 = 2
- Tidskomplexitet = O(2) = O(1) , eftersom 2 är konstant
Hjälputrymme: O(1)
Q2. Hitta summan av alla element i en lista/array
Pseudokoden för att göra det kan anges som:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->array och // n->antal element i array { int summa = 0; för (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 och // n->antal element i array { sum = 0 för i = 0 till n-1 summa = summa + A[i] return summa }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->array och // n->antal element i array { int summa = 0; för (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->array och // n->antal element i array { int summa = 0; för (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->array och // n->antal element i array { låt summa = 0; för (låt 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>
För att förstå tidskomplexiteten för ovanstående kod, låt oss se hur mycket tid varje påstående tar:
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);> Därför den totala kostnaden för att utföra summaoperation
är proteinfett
Summa=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Därför är tidskomplexiteten för ovanstående kod På)
Q3. Hitta summan av alla element i en matris
För denna är komplexiteten en polynomekvation (kvadratisk ekvation för en kvadratisk matris)
- Matris av storlek n*n => Tsum = a.n 2 + b.n + c
- Eftersom Tsum är i ordningen n2, därför Tidskomplexitet = 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>
Tidskomplexitet: På M)
Programmet itererar genom alla element i 2D-matrisen med hjälp av två kapslade loopar. Den yttre slingan itererar n gånger och den inre slingan itererar m gånger för varje iteration av den yttre slingan. Därför är tidskomplexiteten för programmet O(n*m).
Hjälputrymme: På M)
Programmet använder en fast mängd extra utrymme för att lagra 2D-matrisen och några heltalsvariabler. Det utrymme som krävs för 2D-matrisen är nm heltal. Programmet använder också en enda heltalsvariabel för att lagra summan av elementen. Därför är extrarymdskomplexiteten för programmet O(nm + 1), vilket förenklas till O(n*m).
Sammanfattningsvis är programmets tidskomplexitet O(nm), och extrarymdskomplexiteten är också O(nm).
Så från exemplen ovan kan vi dra slutsatsen att tiden för exekvering ökar med den typ av operationer vi gör med hjälp av ingångarna.
Hur jämför man algoritmer?
För att jämföra algoritmer, låt oss definiera några objektiva mått:
- Utförandetider: Inte ett bra mått eftersom körtiderna är specifika för en viss dator.
- Antalet exekverade uttalanden: Inte ett bra mått, eftersom antalet påståenden varierar med programmeringsspråket samt stilen hos den individuella programmeraren.
- Idealisk lösning: Låt oss anta att vi uttrycker körtiden för en given algoritm som en funktion av ingångsstorleken n (d.v.s. f(n)) och jämför dessa olika funktioner motsvarande körtider. Denna typ av jämförelse är oberoende av maskintid, programmeringsstil, etc.
Därför kan en idealisk lösning användas för att jämföra algoritmer.
Relaterade artiklar:
- Tidskomplexitet och rymdkomplexitet
- Analys av algoritmer | Uppsättning 1 (asymptotisk analys)
- Analys av algoritmer | Set 2 (sämsta, genomsnittliga och bästa fall)
- Analys av algoritmer | Uppsättning 3 (asymptotiska notationer)
- Analys av algoritmer | Set 4 (Analys av loopar)
- Analys av algoritm | Uppsättning 5 (Introduktion till amorterad analys)
- Diverse problem med tidskomplexitet
- Öva frågor om tidskomplexitetsanalys
- Att känna till komplexiteten i konkurrenskraftig programmering