Daudzi studenti apjūk, izprotot laika sarežģītības jēdzienu, taču šajā rakstā mēs to izskaidrosim ar ļoti vienkāršu piemēru.
J. Iedomājieties 100 skolēnu klasi, kurā jūs atdevāt pildspalvu vienai personai. Jums ir jāatrod šī pildspalva, nezinot, kam jūs to iedevāt.
Šeit ir daži veidi, kā atrast pildspalvu un O secību.
- O(n 2 ): Jūs ejat un pajautājat pirmajai personai klasē, vai viņam ir pildspalva. Jūs arī pajautājat šai personai par pārējiem 99 cilvēkiem klasē, vai viņiem ir šī pildspalva un tā tālāk,
To mēs saucam par O (n2). - O(n): Iet un jautāt katram skolēnam atsevišķi ir O(N).
- O(log n): Tagad es sadalu klasi divās grupās, pēc tam jautāju: Vai tā atrodas klases kreisajā vai labajā pusē? Tad es ņemu to grupu un sadalu divās daļās un jautāju vēlreiz utt. Atkārtojiet procesu, līdz paliek viens skolēns, kuram ir jūsu pildspalva. Tas ir tas, ko jūs domājat ar O(log n).
Man varētu būt jādara:
- The O(n 2 ) meklē, ja tikai viens students zina, uz kura skolēna ir paslēpta pildspalva .
- The O(n) ja vienam studentam bija pildspalva, un tikai viņi to zināja .
- The O(log n) meklēt, ja visi skolēni zināja , bet pateiktu tikai tad, ja uzminēšu pareizo pusi.
Augšējais O -> sauc Liels - Ak kas ir asimptotisks apzīmējums. Ir arī citi asimptotiski apzīmējumi patīk teta un Omega .
PIEZĪME: Mūs interesē pieauguma temps laika gaitā attiecībā uz programmas izpildes laikā veiktajiem ieguldījumiem.
Vai algoritma/koda laika sarežģītība ir tāda pati kā koda darbības/izpildes laiks?
Algoritma/koda laika sarežģītība ir nē vienāds ar faktisko laiku, kas nepieciešams konkrēta koda izpildei, bet ar paziņojumu izpildes reižu skaitu. Mēs to varam pierādīt, izmantojot laika komanda .
Piemēram: Ierakstiet kodu C/C++ vai jebkurā citā valodā, lai atrastu maksimumu starp N skaitļiem, kur N svārstās no 10, 100, 1000 un 10000. Operētājsistēmām, kuru pamatā ir Linux (Fedora vai Ubuntu), izmantojiet tālāk norādītās komandas:
c programmēšanas piemēru programmas
Lai sastādītu programmu: gcc programma.c – o programma
Lai izpildītu programmu: laiks ./programma
Jūs iegūsit pārsteidzošus rezultātus, piemēram:
- Ja N = 10: jūs varat iegūt 0,5 ms laiku,
- Ja N = 10 000: jūs varat iegūt 0,2 ms laiku.
- Turklāt dažādās iekārtās jūs iegūsit dažādus laikus. Pat ja jūs nesaņemsit vienādus laikus tajā pašā datorā vienam un tam pašam kodam, iemesls ir pašreizējā tīkla slodze.
Tātad, mēs varam teikt, ka faktiskais laiks, kas nepieciešams koda izpildei, ir atkarīgs no mašīnas (neatkarīgi no tā, vai izmantojat Pentium 1 vai Pentium 5), kā arī tā ņem vērā tīkla slodzi, ja jūsu iekārta ir LAN/WAN.
Ko nozīmē algoritma laika sarežģītība?
Tagad rodas jautājums, ja laika sarežģītība nav faktiskais laiks, kas nepieciešams koda izpildei, tad kas tas ir?
Atbilde ir:
Tā vietā, lai izmērītu faktisko laiku, kas nepieciešams katra priekšraksta izpildei kodā, Laika sarežģītība ņem vērā, cik reižu katrs paziņojums tiek izpildīts.
1. piemērs: Apsveriet tālāk sniegto vienkāršo kodu drukāt Hello World
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.> Izvade
Hello World>
Laika sarežģītība: Iepriekš minētajā kodā Hello World uz ekrāna tiek izdrukāts tikai vienu reizi.
Tātad laika sarežģītība ir tāda konstante: O(1) t.i., katru reizi, kad koda izpildei ir nepieciešams konstants laiks, neatkarīgi no tā, kuru operētājsistēmu vai mašīnas konfigurāciju izmantojat.
Palīgtelpa : O(1)
2. piemērs:
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 !!!'); }> Izvade
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Laika sarežģītība: Iepriekš minētajā kodā Hello World !!! ir tikai drukāts n reizes ekrānā, jo n vērtība var mainīties.
Tātad laika sarežģītība ir tāda lineārs: O(n) t.i., katru reizi koda izpildei ir nepieciešams lineārs laiks.
Palīgtelpa: O(1)
3. piemērs:
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.> Izvade
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Laika sarežģītība: O(log2(n))
Palīgtelpa: O(1)
4. piemērs:
tīģeris salīdzinājumā ar lauvuC++
#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 # Šo kodu ir sagatavojis 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.> Izvade
Hello World !!! Hello World !!!>
Laika sarežģītība: O(log(log n))
Palīgtelpa: O(1)
Kā atrast algoritma laika sarežģītību?
Tagad apskatīsim dažus citus piemērus un procesu, lai atrastu algoritma laika sarežģītību:
Piemērs: Apskatīsim mašīnas modeli, kam ir šādas specifikācijas:
- Viens procesors
- 32 biti
- Secīgā izpilde
- 1 laika vienība aritmētiskām un loģiskajām darbībām
- 1 laika vienība piešķiršanas un atgriešanas paziņojumiem
Q1. Iepriekš minētajā mašīnā atrodiet 2 skaitļu summu:
Jebkurai mašīnai divu skaitļu pievienošanas pseidokods būs aptuveni šāds:
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__> Izvade
11>
Laika sarežģītība:
- Iepriekš minētajam kodam būs nepieciešamas 2 laika vienības (nemainīgs):
- viens aritmētiskām darbībām un
- viens atgriešanai. (saskaņā ar iepriekš minētajām konvencijām).
- Tāpēc kopējās izmaksas, lai veiktu summas operāciju ( ) = 1 + 1 = 2
- Laika sarežģītība = O(2) = O(1) , jo 2 ir nemainīgs
Palīgtelpa: O(1)
Q2. Atrodiet visu saraksta/masīva elementu summu
Pseidokodu, lai to izdarītu, var norādīt šādi:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->masīvs un // n->elementu skaits masīvā { int summa = 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->masīvs un // n->elementu skaits masīvā { summa = 0 for i = 0 līdz 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->masīvs un // n->elementu skaits masīvā { int summa = 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->masīvs un // n->elementu skaits masīvā { int summa = 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->masīvs un // n->elementu skaits masīvā { let summa = 0; for (lai 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__> Izvade
14>
Lai saprastu iepriekš minētā koda laika sarežģītību, apskatīsim, cik daudz laika prasīs katrs paziņojums:
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);> Līdz ar to kopējās izmaksas, lai veiktu summas operāciju
Summa = 1 + 2 * (n + 1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O (n)
Tāpēc iepriekš minētā koda laika sarežģītība ir O(n)
Q3. Atrodiet visu matricas elementu summu
Šajā gadījumā sarežģītība ir polinoma vienādojums (kvadrātvienādojums kvadrātveida matricai)
- Matrica ar izmēru n*n => Tsum = a.n 2 + b.n + c
- Tā kā Tsum ir n kārtībā2, tāpēc Laika sarežģītība = 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);> Izvade
43>
Laika sarežģītība: O(n*m)
Programma atkārto visus 2D masīva elementus, izmantojot divas ligzdotas cilpas. Ārējā cilpa atkārtojas n reizes, bet iekšējā cilpa atkārtojas m reizes katrai ārējās cilpas iterācijai. Tāpēc programmas laika sarežģītība ir O(n*m).
Palīgtelpa: O(n*m)
Programma izmanto fiksētu papildu vietas daudzumu, lai saglabātu 2D masīvu un dažus veselus mainīgos lielumus. 2D masīvam nepieciešamā vieta ir nm veseli skaitļi. Programma arī izmanto vienu veselu mainīgo, lai saglabātu elementu summu. Tāpēc programmas palīgtelpas sarežģītība ir O(nm + 1), kas vienkāršojas līdz O(n*m).
Noslēgumā jāsaka, ka programmas laika sarežģītība ir O(nm), un arī palīgtelpas sarežģītība ir O(nm).
Tātad no iepriekš minētajiem piemēriem mēs varam secināt, ka izpildes laiks palielinās līdz ar operāciju veidu, ko veicam, izmantojot ievades.
Kā salīdzināt algoritmus?
Lai salīdzinātu algoritmus, definēsim dažus objektīvus mērus:
- Izpildes laiki: Nav labs pasākums, jo izpildes laiki ir raksturīgi konkrētam datoram.
- Izpildīto paziņojumu skaits: Nav labs rādītājs, jo paziņojumu skaits ir atkarīgs no programmēšanas valodas, kā arī no individuālā programmētāja stila.
- Ideāls risinājums: Pieņemsim, ka mēs izsakām dotā algoritma darbības laiku kā ievades lieluma n funkciju (t.i., f(n)) un salīdzinām šīs dažādās funkcijas, kas atbilst darbības laikiem. Šāda veida salīdzināšana nav atkarīga no mašīnas laika, programmēšanas stila utt.
Tāpēc algoritmu salīdzināšanai var izmantot ideālu risinājumu.
Saistītie raksti:
izņēmumu apstrādes java
- Laika un telpas sarežģītība
- Algoritmu analīze | 1. kopa (asimptotiskā analīze)
- Algoritmu analīze | 2. komplekts (sliktākie, vidējie un labākie gadījumi)
- Algoritmu analīze | 3. kopa (asimptotiskie apzīmējumi)
- Algoritmu analīze | 4. kopa (cilpu analīze)
- Algoritma analīze | 5. kopa (ievads amortizētajā analīzē)
- Dažādas laika sarežģītības problēmas
- Prakses jautājumi par laika sarežģītības analīzi
- Zinot konkursa programmēšanas sarežģītību