Notacja Big O

11.1 Definicja notacji Big O

Notacja Big O to matematyczna notacja używana do opisywania górnej granicy czasu wykonania lub zużycia zasobów przez algorytm w zależności od rozmiaru danych wejściowych. Pomaga określić, jak dobrze algorytm skaluje się i jak jego wydajność zmienia się przy zwiększeniu ilości danych.

Notacja Big O skupia się na najbardziej znaczących aspektach algorytmu, ignorując stałe i mniej znaczące człony, co pozwala skoncentrować się na długoterminowym zachowaniu algorytmu.

Podstawowe notacje:

O(1) — Złożoność stała:

• Czas wykonania algorytmu nie zależy od rozmiaru danych wejściowych.
• Przykład: dostęp do elementu tablicy przez indeks.

O(n) — Złożoność liniowa:

• Czas wykonania algorytmu liniowo zależy od rozmiaru danych wejściowych.
• Przykład: prosty przegląd wszystkich elementów tablicy.

O(log n) — Złożoność logarytmiczna:

• Czas wykonania algorytmu rośnie logarytmicznie wraz ze wzrostem rozmiaru danych wejściowych.
• Przykład: wyszukiwanie binarne w posortowanej tablicy.

O(n^2) — Złożoność kwadratowa:

• Czas wykonania algorytmu kwadratowo zależy od rozmiaru danych wejściowych.
• Przykład: sortowanie bąbelkowe, sortowanie przez wstawianie.

O(2^n) — Złożoność wykładnicza:

• Czas wykonania algorytmu wykładniczo zależy od rozmiaru danych wejściowych.
• Przykład: rozwiązanie problemu plecakowego przez pełne przeszukanie.

Uwaga. Więcej o wyszukiwaniu binarnym, sortowaniu bąbelkowym i „problemie plecakowym” dowiesz się na kolejnych wykładach.

11.2 Interpretacja notacji Big O

Jak interpretować i używać notacji Big O?

Ignorowanie stałych i mniej znaczących członów: Big O opisuje porządek wzrostu funkcji, ignorując stałe i mniej znaczące człony. Na przykład, O(2n) i O(3n) interpretowane są jako O(n).

Porównanie algorytmów: Big O pozwala porównywać algorytmy pod kątem ich efektywności asymptotycznej. Na przykład, algorytm z O(n log n) jest bardziej efektywny niż algorytm z O(n^2) dla bardzo dużych ilości danych.

Analiza najgorszego przypadku: Big O jest zwykle używana do analizy najgorszego przypadku czasu wykonania algorytmu, co pozwala ocenić jego maksymalną złożoność.

Ignorowanie stałych

Zobaczmy przykłady ignorowania stałych i mniej znaczących członów:

Przykład 1. Rozważmy dwie funkcje:

• f(n) = 3n + 2
• g(n) = 5n + 1

Obie funkcje mają złożoność liniową, ponieważ dominującym członem w każdej funkcji jest n. Dlatego obie funkcje są interpretowane jako O(n), mimo różnic w współczynnikach i dodatkowych członach.

Przykład 2. Rozważmy dwie funkcje:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Obie funkcje mają złożoność kwadratową, ponieważ dominującym członem jest n^2. Oba wyrażenia są interpretowane jako O(n^2), mimo różnic w pozostałych członach i współczynnikach.

11.3. Porównanie algorytmów

1. Porównanie algorytmów na bardzo dużych ilościach danych

Przykład 1:

• Algorytm A ma złożoność czasową O(n^2).
• Algorytm B ma złożoność czasową O(n log n).

Dla małych wartości n algorytm A może działać szybciej z powodu mniejszych stałych, ale dla dużych wartości n algorytm B będzie znacznie szybszy, ponieważ jego wzrost jest logarytmiczny, a nie kwadratowy.

Przykład 2:

• Algorytm X ma złożoność czasową O(n).
• Algorytm Y ma złożoność czasową O(1).

Algorytm Y zawsze będzie szybszy, niezależnie od rozmiaru n, ponieważ O(1) oznacza, że czas wykonania algorytmu nie zależy od rozmiaru danych wejściowych.

2. Analiza najgorszego przypadku

Przykład 1:

Algorytm sortowania bąbelkowego ma złożoność czasową O(n^2) w najgorszym przypadku, kiedy tablica jest posortowana w odwrotnej kolejności. Oznacza to, że dla każdego elementu w tablicy potrzebne jest porównanie i być może wymiana z każdym innym elementem.

Przykład 2:

Wyszukiwanie binarne ma złożoność czasową O(log n) w najgorszym przypadku. Oznacza to, że nawet w najgorszym przypadku liczba kroków potrzebnych do znalezienia elementu będzie logarytmicznie zależna od rozmiaru tablicy, co jest bardzo efektywne.

3. Wpływ na wydajność i skalowalność

Przykład 1:

Jeśli mamy dwa algorytmy do przetwarzania danych, jeden z złożonością czasową O(n^2), a drugi z O(n log n), i zwiększamy rozmiar danych z 1000 elementów do 10 000 elementów, różnica w wydajności będzie zauważalna.

• Algorytm z O(n^2) będzie wykonywał około 100 000 000 operacji dla 10 000 elementów.
• Algorytm z O(n log n) będzie wykonywał około 40 000 operacji dla 10 000 elementów.

Przykład 2:

Rozważmy algorytm, który działa w czasie O(2^n). Jeśli zwiększamy rozmiar danych wejściowych z 10 do 20 elementów, liczba operacji rośnie wykładniczo.

• Dla n = 10: 2^10 = 1024 operacji.
• Dla n = 20: 2^20 = 1 048 576 operacji.

To pokazuje, jak szybko złożoność wykładnicza staje się niepraktyczna dla dużych wartości n.