Notacja Big O: główne pojęcia

2.1 Definicja notacji Big O.

Notacja Big O — to matematyczna notacja, używana do opisu górnej granicy czasu wykonywania lub zużycia zasobów algorytmu w zależności od wielkości danych wejściowych. Pomaga określić, jak dobrze algorytm się skalowuje i jak jego wydajność zmienia się przy wzroście ilości danych.

Notacja Big O skupia się na najważniejszych 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) — Stała złożoność:

• Czas wykonywania algorytmu nie zależy od wielkości danych wejściowych.
• Przykład: dostęp do elementu tablicy za pomocą indeksu.

O(n) — Liniowa złożoność:

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

O(log n) — Logarytmiczna złożoność:

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

O(n^2) — Kwadratowa złożoność:

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

O(2^n) — Eksponencjalna złożoność:

• Czas wykonywania algorytmu eksponencjalnie zależy od wielkości danych wejściowych.
• Przykład: rozwiązywanie problemu plecakowego pełnym przeglądem.

2.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 tempo wzrostu funkcji, ignorując stałe i mniej znaczące człony. Na przykład, O(2n) i O(3n) są interpretowane jako O(n).

Porównywanie algorytmów:

Big O pozwala porównywać algorytmy pod względem 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 zazwyczaj służy do analizy najgorszego przypadku czasu wykonywania algorytmu, co pozwala ocenić jego maksymalną złożoność.

Ignorowanie stałych.

Ignorowanie 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ą liniową złożoność, 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ą kwadratową złożoność, 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.

2.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 znacząco 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 wielkości n, ponieważ O(1) oznacza, że czas wykonywania algorytmu nie zależy od wielkości 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, gdy tablica jest posortowana w odwrotnej kolejności. To oznacza, że dla każdego elementu w tablicy konieczne będzie porównanie i, być może, zamiana z każdym innym elementem.

Przykład 2:

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

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

Przykład 1:

Jeśli mamy dwa algorytmy do przetwarzania danych, jeden ze 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 znacząco 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 O(2^n). Jeśli zwiększymy rozmiar danych wejściowych z 10 do 20 elementów, liczba operacji wzrośnie wykładniczo.

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

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