Viele Schüler sind verwirrt, wenn sie das Konzept der Zeitkomplexität verstehen, aber in diesem Artikel werden wir es anhand eines sehr einfachen Beispiels erklären.
F. Stellen Sie sich ein Klassenzimmer mit 100 Schülern vor, in dem Sie einer Person Ihren Stift gegeben haben. Sie müssen diesen Stift finden, ohne zu wissen, wem Sie ihn gegeben haben.
Hier finden Sie einige Möglichkeiten, den Stift und die O-Reihenfolge zu finden.
- An 2 ): Sie gehen und fragen die erste Person in der Klasse, ob sie den Stift hat. Außerdem fragen Sie diese Person nach den anderen 99 Personen im Klassenzimmer, ob sie diesen Stift haben und so weiter.
Das nennen wir O(n2). - An): Es ist O(N), jeden Schüler einzeln zu befragen.
- O(log n): Jetzt teile ich die Klasse in zwei Gruppen auf und frage dann: Ist es auf der linken oder auf der rechten Seite des Klassenzimmers? Dann nehme ich diese Gruppe, teile sie in zwei Teile und frage noch einmal und so weiter. Wiederholen Sie den Vorgang, bis nur noch ein Schüler Ihren Stift hat. Das meinen Sie mit O(log n).
Möglicherweise muss ich Folgendes tun:
- Der An 2 ) sucht ob Nur ein Schüler weiß, bei welchem Schüler der Stift versteckt ist .
- Der An) Wenn Ein Schüler hatte den Stift und nur sie wussten ihn .
- Der O(log n) suchen, wenn Alle Schüler wussten es , würde es mir aber nur sagen, wenn ich die richtige Seite erraten hätte.
Obenstehendes Ö -> heißt Groß – Oh Das ist eine asymptotische Notation. Da sind andere asymptotische Notationen wie Theta Und Omega .
NOTIZ: Uns interessiert die zeitliche Wachstumsrate in Bezug auf die während der Programmausführung erfassten Eingaben.
Ist die zeitliche Komplexität eines Algorithmus/Codes dieselbe wie die Laufzeit/Ausführungszeit des Codes?
Die Zeitkomplexität eines Algorithmus/Codes beträgt nicht entspricht der tatsächlichen Zeit, die zum Ausführen eines bestimmten Codes benötigt wird, aber der Häufigkeit, mit der eine Anweisung ausgeführt wird. Wir können dies beweisen, indem wir die verwenden Zeitbefehl .
Zum Beispiel: Schreiben Sie Code in C/C++ oder einer anderen Sprache, um das Maximum zwischen N Zahlen zu finden, wobei N zwischen 10, 100, 1000 und 10000 variiert. Verwenden Sie für Linux-basierte Betriebssysteme (Fedora oder Ubuntu) die folgenden Befehle:
Modem vs. Router
So kompilieren Sie das Programm: gcc program.c – o Programm
Um das Programm auszuführen: Zeit ./Programm
Sie werden überraschende Ergebnisse erhalten, z. B.:
- Für N = 10: Sie erhalten möglicherweise eine Zeit von 0,5 ms.
- Für N = 10.000: Sie erhalten möglicherweise eine Zeit von 0,2 ms.
- Außerdem erhalten Sie auf verschiedenen Maschinen unterschiedliche Timings. Auch wenn Sie auf demselben Computer für denselben Code nicht die gleichen Timings erhalten, liegt der Grund dafür in der aktuellen Netzwerklast.
Wir können also sagen, dass die Die tatsächliche Zeit, die zum Ausführen des Codes benötigt wird, ist maschinenabhängig (unabhängig davon, ob Sie Pentium 1 oder Pentium 5 verwenden) und berücksichtigt auch die Netzwerklast, wenn sich Ihr Computer im LAN/WAN befindet.
Was versteht man unter der Zeitkomplexität eines Algorithmus?
Nun stellt sich die Frage: Wenn die Zeitkomplexität nicht die tatsächliche Zeit ist, die zum Ausführen des Codes erforderlich ist, was ist sie dann?
Die Antwort ist:
Anstatt die tatsächliche Zeit zu messen, die für die Ausführung jeder Anweisung im Code benötigt wird, Die Zeitkomplexität berücksichtigt, wie oft jede Anweisung ausgeführt wird.
Beispiel 1: Betrachten Sie den folgenden einfachen Code Drucken Sie Hallo Welt
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.> Ausgabe
Hello World>
Zeitkomplexität: Im obigen Code wird Hello World nur einmal auf dem Bildschirm gedruckt.
Die Zeitkomplexität ist also Konstante: O(1) d. h. jedes Mal wird eine konstante Zeit benötigt, um Code auszuführen, unabhängig davon, welches Betriebssystem oder welche Maschinenkonfigurationen Sie verwenden.
Hilfsraum : O(1)
Beispiel 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 !!!'); }> Ausgabe
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Zeitkomplexität: Im obigen Code Hallo Welt !!! wird nur gedruckt n mal auf dem Bildschirm, da sich der Wert von n ändern kann.
Die Zeitkomplexität ist also linear: O(n) d. h. jedes Mal ist eine lineare Zeitspanne erforderlich, um Code auszuführen.
Hilfsraum: O(1)
Beispiel 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.> Ausgabe
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Zeitkomplexität: O(log2(N))
Hilfsraum: O(1)
Beispiel 4:
YouTube-Werbung auf Android blockierenC++
#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 # Dieser Code wurde von akashish__>'> beigesteuertC# Javascript for (let i = 2; i <= 8; i=Math.pow(i,2)) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Ausgabe
Hello World !!! Hello World !!!>
Zeitkomplexität: O(log(log n))
Hilfsraum: O(1)
Wie finde ich die zeitliche Komplexität eines Algorithmus?
Sehen wir uns nun einige andere Beispiele und den Prozess zum Ermitteln der Zeitkomplexität eines Algorithmus an:
Beispiel: Betrachten wir eine Modellmaschine mit folgenden Spezifikationen:
- Einzelprozessor
- 32 Bit
- Sequentielle Ausführung
- 1 Zeiteinheit für arithmetische und logische Operationen
- 1 Zeiteinheit für Zuweisungs- und Rückgabeanweisungen
Q1. Finden Sie die Summe von 2 Zahlen auf der obigen Maschine:
Für jede Maschine sieht der Pseudocode zum Addieren zweier Zahlen etwa so aus:
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__> Ausgabe
11>
Zeitkomplexität:
- Der obige Code benötigt 2 Zeiteinheiten (konstant):
- eine für arithmetische Operationen und
- eine für die Rückgabe. (gemäß den oben genannten Konventionen).
- Daher sind die Gesamtkosten für die Durchführung der Summenoperation ( ) = 1 + 1 = 2
- Zeitkomplexität = O(2) = O(1) , da 2 konstant ist
Hilfsraum: O(1)
Q2. Ermitteln Sie die Summe aller Elemente einer Liste/eines Arrays
Der Pseudocode hierfür kann wie folgt angegeben werden:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->Array und // n->Anzahl der Elemente im Array { int sum = 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 und // n->Anzahl der Elemente im Array { sum = 0 for i = 0 to n-1 sum = sum + A[i] return sum }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->Array und // n->Anzahl der Elemente im Array { int sum = 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 und // n->Anzahl der Elemente im Array { int sum = 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 und // n->Anzahl der Elemente im Array { let sum = 0; für (sei 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__> Ausgabe
14>
Um die zeitliche Komplexität des obigen Codes zu verstehen, sehen wir uns an, wie viel Zeit jede Anweisung benötigt:
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);> Daher die Gesamtkosten für die Durchführung der Summenoperation
Summe=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Daher beträgt die zeitliche Komplexität des obigen Codes An)
Q3. Finden Sie die Summe aller Elemente einer Matrix
In diesem Fall ist die Komplexität eine Polynomgleichung (quadratische Gleichung für eine quadratische Matrix).
- Matrix der Größe n*n => Tsum = a.n 2 + b.n + c
- Da Tsum in der Reihenfolge von n liegt2, daher Zeitkomplexität = 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);> Ausgabe
43>
Zeitkomplexität: O(n*m)
Das Programm durchläuft mithilfe zweier verschachtelter Schleifen alle Elemente im 2D-Array. Die äußere Schleife durchläuft n-mal und die innere Schleife m-mal für jede Iteration der äußeren Schleife. Daher beträgt die zeitliche Komplexität des Programms O(n*m).
Hilfsraum: O(n*m)
Das Programm verwendet eine feste Menge an Hilfsraum zum Speichern des 2D-Arrays und einiger ganzzahliger Variablen. Der für das 2D-Array benötigte Platz beträgt nm ganze Zahlen. Das Programm verwendet außerdem eine einzelne Ganzzahlvariable, um die Summe der Elemente zu speichern. Daher beträgt die Hilfsraumkomplexität des Programms O(nm + 1), was sich zu O(n*m) vereinfacht.
Zusammenfassend beträgt die Zeitkomplexität des Programms O (nm) und die Komplexität des Hilfsraums beträgt ebenfalls O (nm).
Aus den obigen Beispielen können wir schließen, dass die Ausführungszeit mit der Art der Operationen zunimmt, die wir mithilfe der Eingaben durchführen.
Wie vergleicht man Algorithmen?
Um Algorithmen zu vergleichen, definieren wir einige objektive Maße:
- Ausführungszeiten: Kein gutes Maß, da die Ausführungszeiten spezifisch für einen bestimmten Computer sind.
- Die Anzahl der ausgeführten Anweisungen: Kein gutes Maß, da die Anzahl der Anweisungen je nach Programmiersprache und Stil des einzelnen Programmierers variiert.
- Ideale Lösung: Nehmen wir an, dass wir die Laufzeit eines bestimmten Algorithmus als Funktion der Eingabegröße n (d. h. f(n)) ausdrücken und diese verschiedenen Funktionen vergleichen, die den Laufzeiten entsprechen. Diese Art des Vergleichs ist unabhängig von Maschinenzeit, Programmierstil usw.
Daher kann eine ideale Lösung zum Vergleich von Algorithmen verwendet werden.
In Verbindung stehende Artikel:
Sortieralgorithmen für Einfügungen
- Zeitkomplexität und Raumkomplexität
- Analyse von Algorithmen | Satz 1 (Asymptotische Analyse)
- Analyse von Algorithmen | Set 2 (schlechtester, durchschnittlicher und bester Fall)
- Analyse von Algorithmen | Satz 3 (Asymptotische Notationen)
- Analyse von Algorithmen | Satz 4 (Analyse von Schleifen)
- Analyse des Algorithmus | Set 5 (Einführung in die amortisierte Analyse)
- Verschiedene Probleme der Zeitkomplexität
- Übungsfragen zur Zeitkomplexitätsanalyse
- Die Komplexität der Wettbewerbsprogrammierung kennen