logo

TechCodeview

Tijdcomplexiteit begrijpen met eenvoudige voorbeelden

Veel studenten raken in de war als ze het concept van tijdscomplexiteit begrijpen, maar in dit artikel zullen we dit uitleggen met een heel eenvoudig voorbeeld.

V. Stel je een klaslokaal voor met 100 leerlingen, waarin je je pen aan één persoon hebt gegeven. Je moet die pen vinden zonder te weten aan wie je hem hebt gegeven.



Hier zijn enkele manieren om de pen te vinden en wat de O-volgorde is.

  • Op 2 ): Je gaat aan de eerste persoon van de klas vragen of hij de pen heeft. Je vraagt ​​deze persoon ook naar de andere 99 mensen in de klas of ze die pen hebben, enzovoort.
    Dit noemen we O(n2).
  • Op): Elke leerling afzonderlijk gaan vragen is O(N).
  • O(logboek n): Nu verdeel ik de klas in twee groepen en vraag dan: is het aan de linkerkant of aan de rechterkant van het klaslokaal? Dan neem ik die groep en verdeel hem in tweeën en vraag het opnieuw, enzovoort. Herhaal het proces totdat er één leerling overblijft die jouw pen heeft. Dit bedoel je met O(log n).

Ik moet misschien het volgende doen:

  • De Op 2 ) zoekt als slechts één leerling weet op welke leerling de pen verborgen is .
  • De Op) als één student had de pen en alleen zij wisten het .
  • De O(logboek n) zoek als alle studenten wisten het , maar zou het me alleen vertellen als ik de goede kant raadde.

Bovenstaande O -> wordt gebeld Groot – O wat een asymptotische notatie is. Er zijn andere asymptotische notaties leuk vinden theta En Omega .



OPMERKING: We zijn geïnteresseerd in het groeitempo in de loop van de tijd met betrekking tot de input die tijdens de uitvoering van het programma is gebruikt.

Is de tijdscomplexiteit van een algoritme/code hetzelfde als de uitvoerings-/uitvoeringstijd van code?

De tijdscomplexiteit van een algoritme/code is niet gelijk aan de werkelijke tijd die nodig is om een ​​bepaalde code uit te voeren, maar het aantal keren dat een instructie wordt uitgevoerd. We kunnen dit bewijzen door gebruik te maken van de tijd commando .

Bijvoorbeeld: Schrijf code in C/C++ of een andere taal om het maximum tussen N getallen te vinden, waarbij N varieert van 10, 100, 1000 en 10000. Gebruik voor een op Linux gebaseerd besturingssysteem (Fedora of Ubuntu) de onderstaande opdrachten:



touwtje te lang

Om het programma samen te stellen: gcc programma.c – o programma
Om het programma uit te voeren: tijd ./programma

U krijgt verrassende resultaten, bijvoorbeeld:

  • Voor N = 10: u krijgt mogelijk 0,5 ms tijd,
  • Voor N = 10.000: u krijgt mogelijk 0,2 ms tijd.
  • Ook krijgt u verschillende timings op verschillende machines. Zelfs als je niet dezelfde timings op dezelfde machine krijgt voor dezelfde code, is de reden daarachter de huidige netwerkbelasting.

We kunnen dus zeggen dat de De werkelijke tijd die nodig is om code uit te voeren, is machineafhankelijk (of u nu Pentium 1 of Pentium 5 gebruikt) en er wordt ook rekening gehouden met de netwerkbelasting als uw machine zich in LAN/WAN bevindt.

Wat wordt bedoeld met de tijdscomplexiteit van een algoritme?

Nu rijst de vraag of tijdscomplexiteit niet de daadwerkelijke tijd is die nodig is om de code uit te voeren, wat is dat dan wel?

Het antwoord is:

In plaats van de werkelijke tijd te meten die nodig is voor het uitvoeren van elke instructie in de code, Tijdcomplexiteit houdt rekening met het aantal keren dat elke instructie wordt uitgevoerd.

Voorbeeld 1: Overweeg de onderstaande eenvoudige code om afdrukken Hallo wereld

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.>
Uitvoer 
Hello World>

Tijdcomplexiteit: In de bovenstaande code wordt Hello World slechts één keer op het scherm afgedrukt.
De tijdscomplexiteit is dus constante: O(1) dat wil zeggen elke keer dat er een constante hoeveelheid tijd nodig is om code uit te voeren, ongeacht welk besturingssysteem of welke machineconfiguraties u gebruikt.
Hulpruimte : O(1)

Voorbeeld 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 !!!');  }>
Uitvoer 
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Tijdcomplexiteit: In de bovenstaande code Hallo wereld !!! wordt alleen afgedrukt n keer op het scherm, omdat de waarde van n kan veranderen.
De tijdscomplexiteit is dus lineair: O(n) dat wil zeggen dat er elke keer een lineaire hoeveelheid tijd nodig is om code uit te voeren.
Hulpruimte: O(1)

Voorbeeld 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.>
Uitvoer 
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Tijdcomplexiteit: O(logboek2(N))
Hulpruimte: O(1)

Voorbeeld 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('Hallo wereld !!!') i *= i # Deze code is bijgedragen door 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.>
Uitvoer 
Hello World !!! Hello World !!!>

Tijdcomplexiteit: O(logboek(logboek n))
Hulpruimte: O(1)

Hoe vind je de tijdscomplexiteit van een algoritme?

Laten we nu enkele andere voorbeelden bekijken en het proces om de tijdscomplexiteit van een algoritme te vinden:

Voorbeeld: Laten we een modelmachine bekijken die de volgende specificaties heeft:

  • Enkele processor
  • 32 bits
  • Sequentiële uitvoering
  • 1 tijdseenheid voor rekenkundige en logische bewerkingen
  • 1 tijdseenheid voor toewijzings- en retouroverzichten

Q1. Zoek de som van 2 getallen op de bovenstaande machine:

Voor elke machine zal de pseudocode om twee getallen toe te voegen er ongeveer zo uitzien:

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

Tijdcomplexiteit:

besturingssysteem
  • De bovenstaande code duurt 2 tijdseenheden (constant):
    • één voor rekenkundige bewerkingen en
    • één voor retour. (volgens de bovenstaande conventies).
  • Daarom zijn de totale kosten voor het uitvoeren van de sombewerking ( ) = 1 + 1 = 2
  • Tijdcomplexiteit = O(2) = O(1) , aangezien 2 constant is

Hulpruimte: O(1)

Vraag 2. Vind de som van alle elementen van een lijst/array

De pseudocode om dit te doen kan worden gegeven als:

C++ 
#include  using namespace std; int list_Sum(int A[], int n)   // A->array en // n->aantal elementen in array { int som = 0;  voor (int i = 0; ik<= 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 en // n->aantal elementen in array { som = 0 voor i = 0 tot n-1 som = som + A[i] retour som }>
Java 
// Java code for the above approach import java.io.*; class GFG {  static int list_Sum(int[] A, int n)  // A->array en // n->aantal elementen in array { int som = 0;  voor (int i = 0; ik<= 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 en // n->aantal elementen in array { int som = 0;  voor (int i = 0; ik<= 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 en // n->aantal elementen in array {laat som = 0;  voor (laat 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__>
Uitvoer 
14>


Laten we, om de tijdscomplexiteit van de bovenstaande code te begrijpen, eens kijken hoeveel tijd elke instructie in beslag zal nemen:

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

Daarom de totale kosten voor het uitvoeren van de sombewerking

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

Daarom is de tijdscomplexiteit van de bovenstaande code: Op)

wat maakt een pc snel

Q3. Vind de som van alle elementen van een matrix

Voor deze is de complexiteit een polynomiale vergelijking (kwadratische vergelijking voor een vierkante matrix)

  • Matrix van grootte n*n => Tsum = een.n 2 + b.n + c
  • Omdat Tsum in de orde van n staat2, daarom Tijdcomplexiteit = 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);>
Uitvoer 
43>

Tijdcomplexiteit: O(n*m)
Het programma doorloopt alle elementen in de 2D-array met behulp van twee geneste lussen. De buitenste lus itereert n keer en de binnenste lus itereert m keer voor elke iteratie van de buitenste lus. Daarom is de tijdscomplexiteit van het programma O(n*m).

Hulpruimte: O(n*m)
Het programma gebruikt een vaste hoeveelheid hulpruimte om de 2D-array en een paar integer-variabelen op te slaan. De benodigde ruimte voor de 2D-array bestaat uit nm gehele getallen. Het programma gebruikt ook een enkele integer-variabele om de som van de elementen op te slaan. Daarom is de complexiteit van de hulpruimte van het programma O(nm + 1), wat vereenvoudigt tot O(n*m).

Concluderend is de tijdscomplexiteit van het programma O(nm), en de complexiteit van de hulpruimte ook O(nm).

Uit de bovenstaande voorbeelden kunnen we dus concluderen dat de uitvoeringstijd toeneemt met het soort bewerkingen dat we uitvoeren met behulp van de invoer.

Hoe algoritmen vergelijken?

Laten we, om algoritmen te vergelijken, een paar objectieve maatstaven definiëren:

  • Uitvoeringstijden: Geen goede maatregel, aangezien de uitvoeringstijden specifiek zijn voor een bepaalde computer.
  • Het aantal uitgevoerde instructies: Geen goede maatstaf, aangezien het aantal instructies varieert afhankelijk van de programmeertaal en de stijl van de individuele programmeur.
  • Ideale oplossing: Laten we aannemen dat we de looptijd van een bepaald algoritme uitdrukken als een functie van de invoergrootte n (d.w.z. f(n)) en deze verschillende functies vergelijken die overeenkomen met looptijden. Dit soort vergelijking is onafhankelijk van de machinetijd, programmeerstijl, enz.
    Daarom kan een ideale oplossing worden gebruikt om algoritmen te vergelijken.

Gerelateerde artikelen:

  • Tijdcomplexiteit en ruimtecomplexiteit
  • Analyse van algoritmen | Set 1 (asymptotische analyse)
  • Analyse van algoritmen | Set 2 (slechtste, gemiddelde en beste gevallen)
  • Analyse van algoritmen | Set 3 (asymptotische notaties)
  • Analyse van algoritmen | Set 4 (analyse van lussen)
  • Analyse van algoritme | Set 5 (Inleiding tot geamortiseerde analyse)
  • Diverse problemen van tijdcomplexiteit
  • Oefenvragen over tijdcomplexiteitsanalyse
  • De complexiteit van competitief programmeren kennen