Mnoho študentov je zmätených pri pochopení pojmu časová zložitosť, ale v tomto článku si to vysvetlíme na veľmi jednoduchom príklade.
Otázka: Predstavte si triedu so 100 študentmi, v ktorej ste dali svoje pero jednej osobe. Musíte nájsť to pero bez toho, aby ste vedeli, komu ste ho dali.
Tu je niekoľko spôsobov, ako nájsť pero a čo je poradie O.
- O(n 2 ): Idete a spýtate sa prvého človeka v triede, či má pero. Tiež sa tejto osoby spýtate na ostatných 99 ľudí v triede, či majú to pero a tak ďalej,
Toto nazývame O(n2). - O(n): Ísť a pýtať sa každého študenta jednotlivo je O(N).
- O(log n): Teraz rozdelím triedu na dve skupiny a potom sa spýtam: Je to na ľavej alebo pravej strane triedy? Potom zoberiem tú skupinu, rozdelím ju na dve časti a znova sa spýtam, a tak ďalej. Opakujte postup, kým vám nezostane jeden študent, ktorý má vaše pero. Toto máte na mysli pod O(log n).
Možno budem musieť urobiť:
- The O(n 2 ) hľadá ak len jeden žiak vie, na ktorom žiakovi je pero skryté .
- The O(n) ak jeden študent mal pero a len oni to vedeli .
- The O (log n) hľadať ak všetci študenti vedeli , ale povedal by mi to, len keby som uhádol správnu stranu.
Vyššie uvedené O -> sa volá Veľký - Oh čo je asymptotický zápis. Existujú aj iné asymptotické notácie Páči sa mi to theta a Omega .
POZNÁMKA: Zaujíma nás tempo rastu v čase vzhľadom na vstupy prijaté počas vykonávania programu.
Je časová zložitosť algoritmu/kódu rovnaká ako čas spustenia/vykonania kódu?
Časová zložitosť algoritmu/kódu je nie rovná skutočnému času potrebnému na vykonanie konkrétneho kódu, ale počtu vykonaní príkazu. Môžeme to dokázať pomocou časový príkaz .
Napríklad: Napíšte kód v C/C++ alebo v akomkoľvek inom jazyku, aby ste našli maximum medzi N číslami, kde N sa pohybuje od 10, 100, 1000 a 10000. Pre operačný systém založený na Linuxe (Fedora alebo Ubuntu) použite nasledujúce príkazy:
konečný automat
Ak chcete skompilovať program: gcc program.c – o program
Ak chcete spustiť program: čas ./program
Dostanete prekvapivé výsledky, napr.
- Pre N = 10: môžete získať čas 0,5 ms,
- Pre N = 10 000: môžete získať čas 0,2 ms.
- Tiež získate rôzne časovanie na rôznych strojoch. Aj keď nezískate rovnaké časovanie na rovnakom počítači pre rovnaký kód, dôvodom je aktuálne zaťaženie siete.
Môžeme teda povedať, že skutočný čas potrebný na vykonanie kódu závisí od stroja (či už používate Pentium 1 alebo Pentium 5) a tiež zohľadňuje zaťaženie siete, ak je váš počítač v LAN/WAN.
Čo znamená časová zložitosť algoritmu?
Teraz vyvstáva otázka, ak časová zložitosť nie je skutočným časom potrebným na spustenie kódu, čo to potom je?
Odpoveď je:
Namiesto merania skutočného času potrebného na vykonanie každého príkazu v kóde, Časová zložitosť zohľadňuje, koľkokrát sa každý príkaz vykoná.
Príklad 1: Zvážte nižšie uvedený jednoduchý kód vytlačiť Ahoj svet
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.> Výkon
Hello World>
Časová zložitosť: Vo vyššie uvedenom kóde je Hello World vytlačený na obrazovke iba raz.
Časová zložitosť je teda taká konštanta: O(1) t. j. zakaždým, keď je na spustenie kódu potrebný konštantný čas, bez ohľadu na to, aký operačný systém alebo konfiguráciu počítača používate.
Pomocný priestor : O(1)
Príklad 2:
10 z 10C++
#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 !!!'); }> Výkon
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Časová zložitosť: Vo vyššie uvedenom kóde Hello World !!! je iba vytlačená n-krát na obrazovke, pretože hodnota n sa môže meniť.
Časová zložitosť je teda taká lineárny: O(n) t.j. zakaždým je potrebný lineárny čas na vykonanie kódu.
Pomocný priestor: O(1)
Príklad 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.> Výkon
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Časová zložitosť: O(log2(n))
Pomocný priestor: O(1)
Príklad 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('Ahoj svet !!!') i *= i # Tento kód prispel 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.> Výkon
Hello World !!! Hello World !!!>
Časová zložitosť: O(log(log n))
Pomocný priestor: O(1)
Ako zistiť časovú zložitosť algoritmu?
Teraz sa pozrime na niektoré ďalšie príklady a postup na nájdenie časovej zložitosti algoritmu:
Príklad: Zoberme si model stroja, ktorý má nasledujúce špecifikácie:
- Jediný procesor
- 32 bit
- Sekvenčné vykonávanie
- 1 časová jednotka pre aritmetické a logické operácie
- 1 časová jednotka pre príkazy priradenia a návratu
Q1. Nájdite súčet 2 čísel na vyššie uvedenom stroji:
Pre každý počítač bude pseudokód na pridanie dvoch čísel niečo také:
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__> Výkon
11>
Časová zložitosť:
- Vyššie uvedený kód bude trvať 2 jednotky času (konštanta):
- jeden pre aritmetické operácie a
- jeden na vrátenie. (podľa vyššie uvedených konvencií).
- Preto celkové náklady na vykonanie operácie súčtu ( ) = 1 + 1 = 2
- Časová zložitosť = O(2) = O(1) , keďže 2 je konštantná
Pomocný priestor: O(1)
Q2. Nájdite súčet všetkých prvkov zoznamu/pola
Pseudokód na tento účel môže byť uvedený ako:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->pole a // n->počet prvkov v poli { int sum = 0; pre (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->pole a // n->počet prvkov v poli { súčet = 0 pre i = 0 až n-1 súčet = súčet + A[i] návratový súčet }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->pole a // n->počet prvkov v poli { int sum = 0; pre (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->pole a // n->počet prvkov v poli { int sum = 0; pre (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->pole a // n->počet prvkov v poli { nech suma = 0; pre (nech 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__> Výkon
14>
Aby sme pochopili časovú zložitosť vyššie uvedeného kódu, pozrime sa, koľko času zaberie každý príkaz:
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);> Preto celkové náklady na vykonanie operácie súčtu
Súčet = 1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Preto je časová zložitosť vyššie uvedeného kódu O(n)
Q3. Nájdite súčet všetkých prvkov matice
V tomto prípade je zložitosť polynomická rovnica (kvadratická rovnica pre štvorcovú maticu)
- Matica veľkosti n*n => Tsum = a.n 2 + b.n + c
- Keďže Tsum je v poradí n2, teda Časová zložitosť = 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);> Výkon
43>
Časová zložitosť: O(n*m)
Program iteruje všetky prvky v 2D poli pomocou dvoch vnorených slučiek. Vonkajšia slučka sa iteruje n-krát a vnútorná slučka m-krát pre každú iteráciu vonkajšej slučky. Preto je časová náročnosť programu O(n*m).
Pomocný priestor: O(n*m)
Program používa pevné množstvo pomocného priestoru na uloženie 2D poľa a niekoľkých celočíselných premenných. Priestor potrebný pre 2D pole je nm celé čísla. Program tiež používa jednu celočíselnú premennú na uloženie súčtu prvkov. Preto je pomocná priestorová zložitosť programu O(nm + 1), čo sa zjednodušuje na O(n*m).
sqrt java matematika
Záverom možno povedať, že časová zložitosť programu je O(nm) a zložitosť pomocného priestoru je tiež O(nm).
Takže z vyššie uvedených príkladov môžeme usúdiť, že čas vykonania sa zvyšuje s typom operácií, ktoré robíme pomocou vstupov.
Ako porovnávať algoritmy?
Aby sme porovnali algoritmy, definujme niekoľko objektívnych mier:
- Časy realizácie: Nie je to dobré opatrenie, pretože časy vykonávania sú špecifické pre konkrétny počítač.
- Počet vykonaných príkazov: Nie je to dobré opatrenie, pretože počet príkazov sa líši v závislosti od programovacieho jazyka, ako aj štýlu jednotlivého programátora.
- Ideálne riešenie: Predpokladajme, že vyjadríme čas chodu daného algoritmu ako funkciu vstupnej veľkosti n (t.j. f(n)) a porovnáme tieto rôzne funkcie zodpovedajúce časom chodu. Tento druh porovnania je nezávislý od strojového času, štýlu programovania atď.
Preto je možné použiť ideálne riešenie na porovnanie algoritmov.
Súvisiace články:
- Časová zložitosť a priestorová zložitosť
- Analýza algoritmov | Sada 1 (asymptotická analýza)
- Analýza algoritmov | Sada 2 (najhoršie, priemerné a najlepšie prípady)
- Analýza algoritmov | Sada 3 (asymptotické notácie)
- Analýza algoritmov | Sada 4 (Analýza slučiek)
- Analýza algoritmu | Sada 5 (úvod analýzy odpisov)
- Rôzne problémy časovej zložitosti
- Cvičné otázky týkajúce sa analýzy časovej zložitosti
- Poznanie zložitosti konkurenčného programovania