logo

TechCodeview

Razumevanje časovne kompleksnosti s preprostimi primeri

Veliko študentov se zmede pri razumevanju koncepta časovne zapletenosti, toda v tem članku bomo to razložili z zelo preprostim primerom.

Q. Predstavljajte si učilnico s 100 študenti, v kateri ste dali svoje pero eni osebi. To pero moraš najti, ne da bi vedel, komu si ga dal.



Tukaj je nekaj načinov, kako najti pero in kakšen je vrstni red O.

  • O(n 2 ): Pojdi in vprašaj prvega v razredu, če ima pero. Prav tako vprašate to osebo o drugih 99 ljudeh v učilnici, če imajo to pisalo in tako naprej,
    Temu pravimo O(n2).
  • O(n): Iti in vprašati vsakega študenta posebej je O(N).
  • O (log n): Zdaj razdelim razred v dve skupini in nato vprašam: Ali je na levi ali desni strani učilnice? Potem vzamem to skupino in jo razdelim na dve ter ponovno vprašam in tako naprej. Ponavljajte postopek, dokler vam ne ostane en učenec, ki ima vaše pero. To je tisto, kar mislite z O(log n).

Morda bom moral narediti:

  • The O(n 2 ) išče če le en učenec ve, na katerem učencu se skriva pisalo .
  • The O(n) če en učenec je imel pisalo in samo oni so ga poznali .
  • The O(log n) išči če vedeli vsi učenci , vendar bi mi povedal le, če bi uganil pravo stran.

Zgoraj O -> se imenuje Velik – Oh kar je asimptotični zapis. Obstajajo tudi drugi asimptotični zapisi kot theta in Omega .



OPOMBA: Zanima nas stopnja rasti skozi čas glede na vložke, sprejete med izvajanjem programa.

Ali je časovna kompleksnost algoritma/kode enaka času izvajanja/izvajanja kode?

Časovna kompleksnost algoritma/kode je ne enako dejanskemu času, potrebnemu za izvedbo določene kode, ampak številu, kolikokrat se izvede stavek. To lahko dokažemo z uporabo časovni ukaz .

Na primer: Napišite kodo v C/C++ ali katerem koli drugem jeziku, da poiščete največje število med N številkami, kjer se N spreminja od 10, 100, 1000 in 10000. Za operacijski sistem, ki temelji na Linuxu (Fedora ali Ubuntu), uporabite spodnje ukaze:



program python za binarno iskanje

Za prevajanje programa: gcc program.c – o program
Za izvedbo programa: čas ./program

Dobili boste presenetljive rezultate, npr.

  • Za N = 10: lahko dobite čas 0,5 ms,
  • Za N = 10.000: morda dobite čas 0,2 ms.
  • Poleg tega boste na različnih napravah dobili različne čase. Tudi če ne boste dobili enakih časov na istem računalniku za isto kodo, je razlog za to trenutna obremenitev omrežja.

Torej, lahko rečemo, da dejanski čas, potreben za izvedbo kode, je odvisen od stroja (ne glede na to, ali uporabljate Pentium 1 ali Pentium 5) in upošteva tudi obremenitev omrežja, če je vaša naprava v LAN/WAN.

Kaj pomeni časovna kompleksnost algoritma?

Zdaj se postavlja vprašanje, če časovna kompleksnost ni dejanski čas, potreben za izvedbo kode, kaj je potem?

Odgovor je:

Namesto merjenja dejanskega časa, potrebnega za izvajanje vsakega stavka v kodi, Časovna kompleksnost upošteva, kolikokrat se izvede vsak stavek.

Primer 1: Upoštevajte spodnjo preprosto kodo za natisni Pozdravljen 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.>
Izhod 
Hello World>

Časovna zapletenost: V zgornji kodi je Hello World natisnjen samo enkrat na zaslonu.
Torej, časovna kompleksnost je konstanta: O(1) tj. vsakič, ko je za izvajanje kode potreben konstanten čas, ne glede na operacijski sistem ali konfiguracije računalnika, ki jih uporabljate.
Pomožni prostor : O(1)

Primer 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 !!!');  }>
Izhod 
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Časovna zapletenost: V zgornji kodi Hello World !!! je samo natisnjen n-krat na zaslonu, saj se lahko vrednost n spreminja.
Torej, časovna kompleksnost je linearno: O(n) t.j. vsakič je za izvajanje kode potreben linearni čas.
Pomožni prostor: O(1)

Primer 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.>
Izhod 
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Časovna zapletenost: O(log2(n))
Pomožni prostor: O(1)

Primer 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 # To kodo je prispeval 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.>
Izhod 
Hello World !!! Hello World !!!>

Časovna zapletenost: O(log(log n))
Pomožni prostor: O(1)

Kako najti časovno kompleksnost algoritma?

Zdaj pa si oglejmo nekaj drugih primerov in postopek za iskanje časovne kompleksnosti algoritma:

primer: Oglejmo si model stroja, ki ima naslednje specifikacije:

  • En procesor
  • 32 bit
  • Zaporedna izvedba
  • 1 enota časa za aritmetične in logične operacije
  • 1 enota časa za izjave o dodelitvi in ​​vrnitvi

Q1. Poiščite vsoto dveh števil na zgornjem stroju:

shloka mehta

Za kateri koli stroj bo psevdokoda za seštevanje dveh številk približno takšna:

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__>
Izhod 
11>

Časovna zapletenost:

  • Zgornja koda bo trajala 2 enoti časa (konstanta):
    • enega za aritmetične operacije in
    • enega za vrnitev. (v skladu z zgornjimi konvencijami).
  • Zato skupni strošek za izvedbo operacije vsote ( ) = 1 + 1 = 2
  • Časovna kompleksnost = O(2) = O(1) , ker je 2 konstanta

Pomožni prostor: O(1)

Q2. Poiščite vsoto vseh elementov seznama/matrike

Psevdokoda za to je lahko podana kot:

C++ 
#include  using namespace std; int list_Sum(int A[], int n)   // A->matrika in // n->število elementov v matriki { int sum = 0;  za (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->matrika in // n->število elementov v matriki { vsota = 0 za i = 0 do n-1 vsota = vsota + A[i] vrni vsota }>
Java 
// Java code for the above approach import java.io.*; class GFG {  static int list_Sum(int[] A, int n)  // A->matrika in // n->število elementov v matriki { int sum = 0;  za (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->matrika in // n->število elementov v matriki { int sum = 0;  za (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->matrika in // n->število elementov v matriki { naj je vsota = 0;  za (naj bo 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__>
Izhod 
14>


Da bi razumeli časovno zapletenost zgornje kode, poglejmo, koliko časa bo vzel vsak stavek:

C++ 
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);>

Zato skupni strošek za izvedbo operacije vsota

java izboljšana zanka

Vsota=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)

Zato je časovna zapletenost zgornje kode O(n)

Q3. Poiščite vsoto vseh elementov matrike

Za to je kompleksnost polinomska enačba (kvadratna enačba za kvadratno matriko)

  • Matrika velikosti n*n => Tsum = a.n 2 + b.n + c
  • Ker je Tsum v vrstnem redu n2, torej Časovna zapletenost = O(n 2 )
C++ 
#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);>
Izhod 
43>

Časovna zapletenost: O(n*m)
Program ponovi vse elemente v 2D nizu z uporabo dveh ugnezdenih zank. Zunanja zanka se ponovi n-krat, notranja pa m-krat za vsako ponovitev zunanje zanke. Zato je časovna zahtevnost programa O(n*m).

Pomožni prostor: O(n*m)
Program uporablja fiksno količino pomožnega prostora za shranjevanje 2D matrike in nekaj celoštevilskih spremenljivk. Prostor, potreben za 2D polje, je nm celih števil. Program uporablja tudi eno samo celoštevilsko spremenljivko za shranjevanje vsote elementov. Zato je kompleksnost pomožnega prostora programa O(nm + 1), kar je poenostavljeno na O(n*m).

Skratka, časovna zahtevnost programa je O(nm), kompleksnost pomožnega prostora pa prav tako O(nm).

Iz zgornjih primerov lahko sklepamo, da se čas izvajanja povečuje z vrsto operacij, ki jih izvajamo z vhodi.

Kako primerjati algoritme?

Za primerjavo algoritmov določimo nekaj objektivnih meril:

  • Časi izvedbe: Ni dober ukrep, saj so časi izvajanja specifični za določen računalnik.
  • Število izvedenih stavkov: Ni dobro merilo, saj se število stavkov razlikuje glede na programski jezik in slog posameznega programerja.
  • Idealna rešitev: Predpostavimo, da izrazimo čas delovanja danega algoritma kot funkcijo vhodne velikosti n (tj. f(n)) in primerjamo te različne funkcije, ki ustrezajo časom izvajanja. Ta vrsta primerjave je neodvisna od strojnega časa, stila programiranja itd.
    Zato lahko idealno rešitev uporabimo za primerjavo algoritmov.

Povezani članki:

  • Časovna kompleksnost in prostorska kompleksnost
  • Analiza algoritmov | 1. sklop (asimptotična analiza)
  • Analiza algoritmov | 2. niz (najslabši, povprečni in najboljši primeri)
  • Analiza algoritmov | 3. niz (asimptotični zapisi)
  • Analiza algoritmov | 4. niz (analiza zank)
  • Analiza algoritma | 5. sklop (uvod v amortizirano analizo)
  • Razni problemi časovne kompleksnosti
  • Vprašanja za vadbo o analizi časovne kompleksnosti
  • Poznavanje kompleksnosti tekmovalnega programiranja