Blog naprawdę zacny, widzę, że wkładasz w niego dużo czasu, aczkolwiek jedna uwaga co do:
https://mateuszrus.pl/zlozonosc-obliczeniowa/
Mianowicie wyrażenia O, Theta, Omega nie służą określaniu przypadków pesymistycznych, optymistycznych, oczekiwanych:
http://imgur.com/5co9rcXl.png
O, Theta, Omega określają klasy funkcji. Oznacza to, że np. f(n) = n^m należy do każdej klasy abstrakcji O(n^k) gdzie k >= m. Stąd jeśli ilość operacji wykonywanych przez jakiś algorytm określimy funkcją f(n) = n^m to nie prawdą jest, że O(n^{m!}) jest przypadkiem pesymistycznym mimo, że niewątpliwie f należy do tej klasy.
Czyli jeśli mówimy o przypadkach optymistycznym, pesymistycznym etc to powinniśmy dla każdego z tych przypadków podać te klasy abstrakcji (często da się to wyrazić przez thetę, ale przyjeło się pisać same O(function)).
Przykład: Insertion Sort
Jego złożoność w przypadku pesymistycznym oraz oczekiwanym (UWAGA! "Oczekiwany" to nie jest tak "jak nam się wydaje" - tzn z reguły jest ale nie zawsze tak musi być, w tym wypadku należy policzyć wartości oczekiwane parametrów wpływających na złożoność przy użyciu rachunku prawdopodobieństwa - w przypadku insertion sorta jest to ilość inwersji) to jest O(n^2) (a nawet theta(n^2), ale w przykadku optymistycznym, gdzie liczba inwersji jest asymptotycznie liniowa względem liczby elementów w ciągu, dostajemy algorytm O(n) ( a konkretniej Omega(n) oraz O(n) czyli Theta(n)).
Jeśli ktoś by napisał, że
Insertion Sort: jest O(n^2), Omega(n) to by nie skłamał ale równie dobrze by nie skłamał gdyby napisał, że insertion-sort jest O(n^10 * n!), Omega(1). A jeżeli ktoś by napisał, że ten alg jest Theta(coś) to by nie miał racji, bo bez dodatkowych założeń nie wyrazimy jest złożoności w thecie.
