Notacja dużego O to potężne narzędzie stosowane w informatyce do opisu złożoności czasowej lub przestrzennej algorytmów. Zapewnia ujednolicony sposób porównywania wydajności różnych algorytmów pod względem ich najgorszej wydajności. Zrozumienie Notacja dużego O jest niezbędna do analizowania i projektowania wydajnych algorytmów.

W tym samouczku omówimy podstawy Notacja dużego O , jego znaczenie i sposób analizy złożoności stosowanych algorytmów Duże O .

Spis treści

• Co to jest notacja Big-O?
• Definicja notacji Big-O:
• Dlaczego notacja dużego O jest ważna?
• Właściwości notacji dużego O
• Typowe notacje Big-O
• Jak określić notację dużego O?
• Matematyczne przykłady analizy czasu wykonania
• Algorytmiczne przykłady analizy czasu wykonania
• Klasy algorytmów z liczbą operacji i czasem wykonania
• Porównanie notacji dużego O, notacji dużego Ω (Omega) i notacji dużego θ (Theta)
• Często zadawane pytania dotyczące notacji dużego O

Co to jest notacja Big-O?

Duże-O , powszechnie określane jako Kolejność , to sposób na wyrażenie Górna granica złożoności czasowej algorytmu, ponieważ analizuje on najgorszy przypadek sytuacja algorytmu. Zapewnia Górna granica od czasu potrzebnego algorytmowi pod względem rozmiaru danych wejściowych. Jest oznaczony jako O(f(n)) , Gdzie f(n) to funkcja reprezentująca liczbę operacji (kroków), które wykonuje algorytm, aby rozwiązać problem wielkości N .

Notacja dużego O służy do opisu wydajności lub złożoności algorytmu. W szczególności opisuje Najgorszy scenariusz pod względem czas Lub złożoność przestrzeni.

Ważny punkt:

• Notacja dużego O opisuje jedynie asymptotyczne zachowanie funkcji, a nie jej dokładną wartość.
• The Notacja dużego O można wykorzystać do porównania wydajności różnych algorytmów lub struktur danych.

Definicja notacji Big-O:

Biorąc pod uwagę dwie funkcje f(n) I g(n) , tak mówimy f(n) Jest O(g(n)) jeśli istnieją stałe c> 0 I N ₀ >= 0 takie, że f(n) <= c*g(n) dla wszystkich n>= n ₀ .

Mówiąc prościej, f(n) Jest O(g(n)) Jeśli f(n) rośnie nie szybciej niż c*g(n) dla wszystkich n>= n₀gdzie c i n₀są stałymi.

10 z 40

Dlaczego notacja dużego O jest ważna?

Notacja dużego O to notacja matematyczna używana do opisu złożoności czasowej lub wydajności algorytmu w najgorszym przypadku, bądź też najgorszej złożoności przestrzennej struktury danych. Umożliwia porównanie wydajności różnych algorytmów i struktur danych oraz przewidzenie, jak będą się one zachowywać wraz ze wzrostem rozmiaru danych wejściowych.

Notacja dużego O jest ważna z kilku powodów:

• Notacja dużego O jest ważna, ponieważ pomaga analizować wydajność algorytmów.
• Umożliwia opisanie, w jaki sposób czas wykonania Lub wymagania przestrzenne algorytmu rośnie wraz ze wzrostem rozmiaru danych wejściowych.
• Pozwala programistom porównać różne algorytmy i wybrać najbardziej efektywny dla konkretnego problemu.
• Pomaga w zrozumieniu skalowalności algorytmów i przewidywaniu ich działania w miarę wzrostu rozmiaru danych wejściowych.
• Umożliwia programistom optymalizację kodu i poprawę ogólnej wydajności.

Właściwości notacji dużego O:

Poniżej znajduje się kilka ważnych właściwości notacji Big O:

1. Zwrotność:

Dla dowolnej funkcji f(n), f(n) = O(f(n)).

Przykład:

f(n) = n², wówczas f(n) = O(n²).

2. Przechodniość:

Jeśli f(n) = O(g(n)) i g(n) = O(h(n)), to f(n) = O(h(n)).

Przykład:

f(n) = n³, g(n) = n², h(n) = n⁴. Wtedy f(n) = O(g(n)) i g(n) = O(h(n)). Zatem f(n) = O(h(n)).

3. Stały współczynnik:

Dla dowolnej stałej c> 0 i funkcji f(n) i g(n), jeśli f(n) = O(g(n)), to cf(n) = O(g(n)).

Przykład:

f(n) = n, g(n) = n². Wtedy f(n) = O(g(n)). Zatem 2f(n) = O(g(n)).

4. Reguła sumy:

Jeśli f(n) = O(g(n)) i h(n) = O(g(n)), to f(n) + h(n) = O(g(n)).

Przykład:

f(n) = n², g(n) = n³, h(n) = n⁴. Wtedy f(n) = O(g(n)) i h(n) = O(g(n)). Zatem f(n) + h(n) = O(g(n)).

5. Zasada dotycząca produktu:

Jeśli f(n) = O(g(n)) i h(n) = O(k(n)), to f(n) * h(n) = O(g(n) * k(n)) .

Przykład:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Wtedy f(n) = O(g(n)) i h(n) = O(k(n)). Dlatego f(n) * h(n) = O(g(n) * k(n)) = O(n⁵).

6. Zasada składu:

Jeśli f(n) = O(g(n)) i g(n) = O(h(n)), to f(g(n)) = O(h(n)).

Przykład:

f(n) = n², g(n) = n, h(n) = n³. Wtedy f(n) = O(g(n)) i g(n) = O(h(n)). Zatem f(g(n)) = O(h(n)) = O(n³).

Typowe notacje Big-O:

Notacja Big-O to sposób pomiaru złożoności czasowej i przestrzennej algorytmu. Opisuje górną granicę złożoności w najgorszym przypadku. Przyjrzyjmy się różnym typom złożoności czasowej:

1. Liniowa złożoność czasu: złożoność dużego O(n).

Liniowa złożoność czasowa oznacza, że ​​czas działania algorytmu rośnie liniowo wraz z rozmiarem danych wejściowych.

formatowanie ciągu Java

Rozważmy na przykład algorytm, który przechodzi przez tablicę, aby znaleźć określony element :

bool findElement(int arr[], int n, int key) {  for (int i = 0; i < n; i++) {  if (arr[i] == key) {  return true;  }  }  return false; }>

2. Logarytmiczna złożoność czasu: złożoność dużego O(log n).

Logarytmiczna złożoność czasowa oznacza, że ​​czas działania algorytmu jest proporcjonalny do logarytmu wielkości wejściowej.

Na przykład: Algorytm wyszukiwania binarnego ma logarytmiczną złożoność czasową:

int binarySearch(int arr[], int l, int r, int x) {  if (r>= l) { int środek = l + (r - l) / 2;  if (arr[mid] == x) return mid;  if (arr[mid]> x) return binarySearch(arr, l, mid - 1, x);  return binarySearch(arr, mid + 1, r, x);  } zwróć -1; }>

3. Złożoność czasu kwadratowego: duże O(n²) Złożoność

Kwadratowa złożoność czasowa oznacza, że ​​czas działania algorytmu jest proporcjonalny do kwadratu rozmiaru danych wejściowych.

Na przykład prosty algorytm sortowania bąbelkowego ma kwadratową złożoność czasową:

void bubbleSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {  for (int j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]);  } } } }>

4. Złożoność czasu sześciennego: duże O(n³) Złożoność

Złożoność czasu sześciennego oznacza, że ​​czas działania algorytmu jest proporcjonalny do sześcianu rozmiaru wejściowego.

Na przykład naiwny algorytm mnożenia macierzy ma sześcienną złożoność czasową:

void multiply(int mat1[][N], int mat2[][N], int res[][N]) {  for (int i = 0; i < N; i++) {  for (int j = 0; j < N; j++) {  res[i][j] = 0;  for (int k = 0; k < N; k++)  res[i][j] += mat1[i][k] * mat2[k][j];  }  } }>

5. Złożoność czasu wielomianowego: duże O(n^k) Złożoność

Wielomianowa złożoność czasowa odnosi się do złożoności czasowej algorytmu, którą można wyrazić jako funkcję wielomianową rozmiaru wejściowego N . W Dużym O W notacji mówi się, że algorytm ma wielomianową złożoność czasową, jeżeli jego złożoność czasowa wynosi NA ^k ) , Gdzie k jest stałą i reprezentuje stopień wielomianu.

Algorytmy o złożoności wielomianowej są ogólnie uważane za wydajne, ponieważ czas działania rośnie w rozsądnym tempie wraz ze wzrostem rozmiaru danych wejściowych. Typowe przykłady algorytmów o wielomianowej złożoności czasowej obejmują liniowa złożoność czasowa O(n) , kwadratowa złożoność czasowa O(n ² ) , I sześcienna złożoność czasowa O(n ³ ) .

6. Wykładnicza złożoność czasu: duże O(2^N) Złożoność

Wykładnicza złożoność czasowa oznacza, że ​​czas działania algorytmu podwaja się przy każdym dodaniu zbioru danych wejściowych.

Na przykład problem generowanie wszystkich podzbiorów zbioru ma wykładniczą złożoność czasową:

void generateSubsets(int arr[], int n) {  for (int i = 0; i < (1 << n); i++) {  for (int j = 0; j < n; j++) {  if (i & (1 << j)) {  cout << arr[j] << ' ';  }  }  cout << endl;  } }>

Złożoność czasowa silni: złożoność dużego O(n!).

Złożoność czasowa silni oznacza, że ​​czas działania algorytmu rośnie silniowo wraz z rozmiarem danych wejściowych. Jest to często widoczne w algorytmach, które generują wszystkie permutacje zbioru danych.

Oto przykład algorytmu złożoności czasowej silni, który generuje wszystkie permutacje tablicy:

void permute(int* a, int l, int r) {  if (l == r) {  for (int i = 0; i <= r; i++) {  cout << a[i] << ' ';  }  cout << endl;  }  else {  for (int i = l; i <= r; i++) {  swap(a[l], a[i]);  permute(a, l + 1, r);  swap(a[l], a[i]); // backtrack  }  } }>

Jeśli naszkicujemy najczęstsze przykłady notacji Big O, otrzymamy wykres taki jak ten:

Jak określić notację dużego O?

Notacja dużego O jest notacją matematyczną używaną do opisu zachowanie asymptotyczne funkcji, w miarę jak jej wartość rośnie nieskończenie duża. Umożliwia scharakteryzowanie wydajności algorytmów i struktur danych.

Kroki, aby określić notację dużego O:

1. Zidentyfikuj termin dominujący:

• Zbadaj funkcję i zidentyfikuj termin o najwyższym rzędzie wzrostu w miarę wzrostu wielkości wejściowej.
• Zignoruj ​​wszelkie stałe czynniki lub terminy niższego rzędu.

2. Określ kolejność wzrostu:

• Kolejność wzrostu terminu dominującego określa notację Big O.

3. Zapisz notację dużego O:

• Notację Big O zapisuje się jako O(f(n)), gdzie f(n) reprezentuje termin dominujący.
• Na przykład, jeśli dominującym terminem jest n^2, notacja dużego O będzie miała postać O(n^2).

4. Uprość notację (opcjonalnie):

• W niektórych przypadkach Marka Big O n można uprościć, usuwając stałe czynniki lub stosując bardziej zwięzłą notację.
• Na przykład, O(2n) można uprościć do NA).

Przykład:

znak do napisania Java

Funkcja: f(n) = 3n³+ 2n²+ 5n + 1

1. Termin dominujący: 3n³
2. Kolejność wzrostu: sześcienna (n³)
3. Notacja dużego O: O(n³)
4. Uproszczona notacja: O(n³)

Matematyczne przykłady analizy czasu wykonania:

Poniższa tabela ilustruje analizę czasu wykonywania różnych rzędów algorytmów w miarę wzrostu rozmiaru danych wejściowych (n).

Algorytmiczne przykłady analizy czasu wykonania:

Poniższa tabela kategoryzuje algorytmy na podstawie ich złożoności w czasie wykonywania i zawiera przykłady dla każdego typu.

Klasy algorytmów z liczbą operacji i czasem wykonania:

Poniżej znajdują się klasy algorytmów i czasy ich wykonywania na komputerze wykonującym 1 milion operacji na sekundę (1 s = 10 ⁶ µs = 10 ³ ms) :

Porównanie notacji dużego O, notacji dużego Ω (Omega) i notacji dużego θ (Theta):

Poniżej znajduje się tabela porównująca notację Big O, notację Ω (Omega) i notację θ (Theta):

W każdym zapisie:

• f(n) reprezentuje analizowaną funkcję, zazwyczaj złożoność czasową algorytmu.
• g(n) reprezentuje określoną funkcję, która ogranicza f(n) .
• C, C1​, I C2 są stałymi.
• N ₀ ​ to minimalny rozmiar danych wejściowych, powyżej którego zachodzi nierówność.

Notacje te służą do analizy algorytmów na ich podstawie najgorszy przypadek (duże O) , najlepszy przypadek (Ω) , I przypadek średni (θ) scenariusze.

Często zadawane pytania dotyczące notacji dużego O:

Pytanie 1. Co to jest notacja dużego O?

Odpowiedź: Notacja dużego O to notacja matematyczna używana do opisania górnej granicy złożoności czasowej algorytmu w kategoriach jej wzrostu w stosunku do rozmiaru danych wejściowych.

Pytanie 2. Dlaczego notacja dużego O jest ważna?

Odpowiedź: Pomaga nam analizować i porównywać wydajność algorytmów, koncentrując się na najgorszym scenariuszu i rozumiejąc, jak ich wydajność skaluje się wraz z rozmiarem danych wejściowych.

Pytanie 3. Jak obliczana jest notacja dużego O?

Odpowiedź: Notację Big O określa się poprzez identyfikację dominującej operacji w algorytmie i wyrażenie jej złożoności czasowej w kategoriach n, gdzie n oznacza rozmiar wejściowy.

Pytanie 4. Co oznacza O(1) w notacji Big O?

Odpowiedź: O(1) oznacza stałą złożoność czasową, wskazując, że czas wykonania algorytmu nie zmienia się niezależnie od rozmiaru danych wejściowych.

Pytanie 5. Jakie jest znaczenie różnych złożoności Wielkiego O, takich jak O(log n) lub O(n^2)?

Odpowiedź: Różne złożoności, takie jak O(log n) lub O(n^2), reprezentują sposób, w jaki skaluje się wydajność algorytmu wraz ze wzrostem rozmiaru danych wejściowych, zapewniając wgląd w jego wydajność i skalowalność.

Pytanie 6. Czy notację dużego O można zastosować również do złożoności przestrzeni?

Odpowiedź: Tak, notacji Big O można również używać do analizowania i opisywania złożoności przestrzennej algorytmu, wskazując, ile pamięci wymaga w stosunku do rozmiaru wejściowego.

Powiązany artykuł:

• Przykłady analizy Big-O
• Projektowanie i analiza algorytmów
• Rodzaje notacji asymptotycznych w analizie złożoności algorytmów
• Analiza algorytmów | Notacja Big – Ω (Big-Omega).
• Analiza algorytmów | małe oznaczenia o i małe omega