Wielu uczniów ma trudności ze zrozumieniem pojęcia złożoności czasowej, ale w tym artykule wyjaśnimy to na bardzo prostym przykładzie.
P. Wyobraź sobie klasę liczącą 100 uczniów, w której oddałeś swój długopis jednej osobie. Musisz znaleźć ten długopis, nie wiedząc, komu go dałeś.
Oto kilka sposobów na znalezienie pióra i kolejność O.
- NA 2 ): Idziesz i pytasz pierwszą osobę w klasie, czy ma długopis. Zapytaj tę osobę także o pozostałych 99 osób w klasie, czy mają ten długopis itd.,
To właśnie nazywamy O(n2). - NA): Pójście i zapytanie każdego ucznia indywidualnie to O(N).
- O(log n): Teraz dzielę klasę na dwie grupy i pytam: czy to jest po lewej, czy po prawej stronie klasy? Następnie biorę tę grupę, dzielę ją na dwie części i pytam ponownie, i tak dalej. Powtarzaj ten proces, aż zostaniesz z jednym uczniem, który ma Twój długopis. To właśnie masz na myśli mówiąc O(log n).
Być może będę musiał zrobić:
- The NA 2 ) szuka, jeśli tylko jeden uczeń wie, któremu uczniowi ukryte jest pióro .
- The NA) Jeśli jeden uczeń miał pióro i tylko oni o tym wiedzieli .
- The O(log n) szukaj, jeśli wszyscy uczniowie wiedzieli , ale powiedziałby mi tylko wtedy, gdybym odgadł prawą stronę.
Powyższe O -> nazywa się Duży – O co jest notacją asymptotyczną. Są inne notacje asymptotyczne tak jak teta I Omega .
NOTATKA: Interesuje nas tempo wzrostu w czasie w odniesieniu do nakładów poniesionych w trakcie realizacji programu.
Czy złożoność czasowa algorytmu/kodu jest taka sama jak czas wykonania/wykonania kodu?
Złożoność czasowa algorytmu/kodu wynosi nie równy rzeczywistemu czasowi wymaganemu do wykonania określonego kodu, ale liczbie wykonań instrukcji. Możemy to udowodnić za pomocą polecenie czasu .
Na przykład: Napisz kod w C/C++ lub dowolnym innym języku, aby znaleźć maksimum pomiędzy N liczbami, gdzie N waha się od 10, 100, 1000 i 10000. W przypadku systemu operacyjnego opartego na systemie Linux (Fedora lub Ubuntu) użyj poniższych poleceń:
łączność z Javą
Aby skompilować program: gcc program.c – o program
Aby wykonać program: czas./program
Otrzymasz zaskakujące rezultaty, tj.:
- Dla N = 10: możesz uzyskać czas 0,5 ms,
- Dla N = 10 000: możesz uzyskać czas 0,2 ms.
- Otrzymasz także różne czasy na różnych maszynach. Nawet jeśli nie uzyskasz takich samych czasów na tej samej maszynie dla tego samego kodu, przyczyną tego jest bieżące obciążenie sieci.
Można więc powiedzieć, że rzeczywisty czas wymagany do wykonania kodu zależy od maszyny (niezależnie od tego, czy używasz Pentium 1, czy Pentium 5), a także uwzględnia obciążenie sieci, jeśli twój komputer znajduje się w sieci LAN/WAN.
Co oznacza złożoność czasowa algorytmu?
Teraz pojawia się pytanie, jeśli złożoność czasowa nie jest rzeczywistym czasem wymaganym do wykonania kodu, to czym jest?
Odpowiedź to:
Zamiast mierzyć rzeczywisty czas wymagany na wykonanie każdej instrukcji w kodzie, Złożoność czasowa uwzględnia, ile razy każda instrukcja jest wykonywana.
Przykład 1: Rozważ poniższy prosty kod drukuj Witaj, świecie
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; }> Jawa 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.> Wyjście
Hello World>
Złożoność czasowa: W powyższym kodzie Hello World jest wyświetlane tylko raz na ekranie.
Zatem złożoność czasowa jest stała: O(1) tj. za każdym razem, gdy wykonanie kodu wymaga stałej ilości czasu, niezależnie od używanego systemu operacyjnego i konfiguracji komputera.
Przestrzeń pomocnicza : O(1)
Przykład 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 !!!
'); } }> Jawa 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 !!!'); }> Wyjście
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Złożoność czasowa: W powyższym kodzie Hello World !!! jest tylko drukowany n razy na ekranie, ponieważ wartość n może się zmieniać.
Zatem złożoność czasowa jest liniowy: O(n) tj. za każdym razem do wykonania kodu wymagana jest liniowa ilość czasu.
Przestrzeń pomocnicza: O(1)
Przykład 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> Jawa 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.> Wyjście
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Złożoność czasowa: O(log2(N))
Przestrzeń pomocnicza: O(1)
Przykład 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> Jawa 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 # Ten kod został stworzony przez 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.> Wyjście
Hello World !!! Hello World !!!>
Złożoność czasowa: O(log(log n))
Przestrzeń pomocnicza: O(1)
Jak znaleźć złożoność czasową algorytmu?
Przyjrzyjmy się teraz innym przykładom i procesowi wyznaczania złożoności czasowej algorytmu:
Przykład: Rozważmy model maszyny, który ma następujące specyfikacje:
- Pojedynczy procesor
- 32-bitowy
- Wykonanie sekwencyjne
- 1 jednostka czasu dla operacji arytmetycznych i logicznych
- 1 jednostka czasu na instrukcje przypisania i zwrotu
Pytanie 1. Znajdź sumę 2 liczb na powyższej maszynie:
W przypadku dowolnej maszyny pseudokod umożliwiający dodanie dwóch liczb będzie wyglądał mniej więcej 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 }> Jawa // 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__> Wyjście
11>
Złożoność czasowa:
sąsiednie kąty
- Powyższy kod zajmie 2 jednostki czasu (stała):
- jeden do operacji arytmetycznych i
- jeden na powrót. (zgodnie z powyższymi konwencjami).
- Zatem całkowity koszt wykonania operacji sumowania ( ) = 1 + 1 = 2
- Złożoność czasowa = O(2) = O(1) , ponieważ 2 jest stałe
Przestrzeń pomocnicza: O(1)
Pytanie 2. Znajdź sumę wszystkich elementów listy/tablicy
Pseudokod umożliwiający to można podać jako:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->tablica i // n->liczba elementów w tablicy { int sum = 0; for (int i = 0; tj<= 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->tablica i // n->liczba elementów w tablicy { suma = 0 dla i = 0 do n-1 suma = suma + A[i] zwracana suma }> Jawa // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->tablica i // n->liczba elementów w tablicy { int sum = 0; for (int i = 0; tj<= 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->tablica i // n->liczba elementów w tablicy { int sum = 0; for (int i = 0; tj<= 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->tablica i // n->liczba elementów w tablicy { niech suma = 0; dla (niech i = 0; tj<= 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__> Wyjście
14>
Aby zrozumieć złożoność czasową powyższego kodu, zobaczmy, ile czasu zajmie każda instrukcja:
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 }> Jawa 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);> Zatem całkowity koszt wykonania operacji sumowania
Suma=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Zatem złożoność czasowa powyższego kodu wynosi NA)
szybkie sortowanie
Pytanie 3. Znajdź sumę wszystkich elementów macierzy
W tym przypadku złożoność jest równaniem wielomianowym (równanie kwadratowe dla macierzy kwadratowej)
- Macierz wielkości n*n => Tsum = a.n 2 + b.n + c
- Ponieważ Tsum jest rzędu n2, W związku z tym Złożoność czasowa = 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__> Jawa /*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);> Wyjście
43>
Złożoność czasowa: O(n*m)
Program iteruje po wszystkich elementach tablicy 2D, używając dwóch zagnieżdżonych pętli. Zewnętrzna pętla iteruje n razy, a wewnętrzna pętla iteruje m razy dla każdej iteracji zewnętrznej pętli. Zatem złożoność czasowa programu wynosi O(n*m).
Przestrzeń pomocnicza: O(n*m)
Program wykorzystuje stałą ilość przestrzeni pomocniczej do przechowywania tablicy 2D i kilku zmiennych całkowitych. Miejsce wymagane dla tablicy 2D to nm liczb całkowitych. Program używa również pojedynczej zmiennej całkowitej do przechowywania sumy elementów. Dlatego złożoność programu w przestrzeni pomocniczej wynosi O(nm + 1), co upraszcza się do O(n*m).
Podsumowując, złożoność czasowa programu wynosi O(nm), a złożoność przestrzeni pomocniczej również wynosi O(nm).
Z powyższych przykładów możemy zatem wywnioskować, że czas wykonania zwiększa się wraz z rodzajem operacji, jakie wykonujemy na danych wejściowych.
Jak porównywać algorytmy?
Aby porównać algorytmy, zdefiniujmy kilka miar obiektywnych:
- Czasy realizacji: Nie jest to dobry miernik, ponieważ czasy wykonania są specyficzne dla konkretnego komputera.
- Liczba wykonanych instrukcji: Nie jest to dobra miara, ponieważ liczba instrukcji różni się w zależności od języka programowania, a także stylu indywidualnego programisty.
- Idealne rozwiązanie: Załóżmy, że wyrażamy czas działania danego algorytmu jako funkcję rozmiaru wejściowego n (tj. f(n)) i porównujemy te różne funkcje odpowiadające czasom działania. Tego rodzaju porównanie jest niezależne od czasu pracy maszyny, stylu programowania itp.
Można zatem zastosować idealne rozwiązanie do porównania algorytmów.
Powiązane artykuły:
- Złożoność czasu i złożoność przestrzeni
- Analiza algorytmów | Zbiór 1 (analiza asymptotyczna)
- Analiza algorytmów | Zestaw 2 (najgorszy, średni i najlepszy przypadek)
- Analiza algorytmów | Zbiór 3 (notacje asymptotyczne)
- Analiza algorytmów | Zestaw 4 (Analiza pętli)
- Analiza algorytmu | Zestaw 5 (wprowadzenie do analizy zamortyzowanej)
- Różne problemy złożoności czasu
- Ćwicz pytania dotyczące analizy złożoności czasu
- Znajomość złożoności programowania konkurencyjnego