Do określenia wydajności algorytmu wykorzystywana jest notacja dużego O. Przykładowo O(n!), O(n) czy O(n+1). Może ona określać zarówno ilość potrzebnych operacji (określana czasami złożonością czasową) lub też ilość potrzebnej pamięci do realizacji algorytmu.
Jak rozumieć taką notację?
| Oznaczenie | Interpretacja |
|---|---|
| O(n2) | Dla n elementowej kolekcji będzie potrzebne n2 operacji (lub też n2 jednostek pamięci) |
| O(n+1) | Dla n elementowej kolekcji będzie potrzebne n+1 operacji (lub też n+1 jednostek pamięci) |
Przykładowo jeśli algorytm wykonuje się z wydajnością O(n!) operacji. Oznaczać to będzie, że dla kolekcji składającej się z 4 elementów, będzie wykonanych 24 operacji (bo 4! to inaczej 4*3*2*1 a to się równa 24. A dla kolekcji składającej się już 5 elementów, będzie to 120.
Najlepszy, średni i najgorszy przypadek
Należy zaznaczyć, że ilość wykonanych operacji (lub też wykorzystanych jednostek pamięci) często jest różna w zależności od argumentów wejściowych. Przykładowo przy sortowaniu kolekcji liczb:
1,2,3
powiedzmy, że algorytm X wykona 2 operacje (bo elementy są już posortowane). Zaś dla kolekcji:
3,2,1
będzie to już 9 operacji.
Stąd rozróżnia się:
najlepszą złożoność – ile czasu (lub pamięci) zajmie wykonanie, przy idealnie (dla danego algorytmu) ułożonych argumentach wejściowych. Często zamiast O stosuje się Ω.
średnią złożoność – ile czasu (lub pamięci) średnio zajmie wykonanie. Często zamiast O stosuje się θ.
najgorszą złożoność – ile czasu (lub pamięci) zajmie wykonanie, przy najbardziej niekorzystnie ułożonych argumentach wejściowych.
Jak sobie radzą wybrane algorytmy sortowania
| Nazwa algorytmu | Najlepsza złożoność (Ω) | Średnia złożoność (θ) | Najgorsza złożoność (O) |
|---|---|---|---|
| Sortowanie bąbelkowe | Ω(n) | θ(n2) | O(n2) |
| Sortowanie szybkie | Ω(n log (n)) | θ(n log (n)) | O(n2) |
| Sortowanie Shella | Ω(n log (n)) | θ(n log (n)) | O(n2) |
| Binarne drzewo poszukiwań | Ω(n) | θ(n log (n)) | O(n2) |
Kto to wymyślił?
Zapis dużego O przypisuje się głównie dwóm niemieckim matematykom Paul Gustav Heinrich Bachmann oraz Edmund Georg Hermann Landau. Chociaż pracowali nad nią także inni.
Warto zajrzeć
1. https://en.wikipedia.org/wiki/Big_O_notation
2. https://miroslawzelent.pl/kurs-python/algorytmy-sortowania/