Definicje bez problemu znajdziesz w sieci - jak również rozróżnienie na złożoności optymistyczne, pesymistyczne, oczekiwane, jak wyznaczać złożoność itd.
Na chłopski rozum złożoność obliczeniowa mówi, jak szybko czas rozwiązania (jako liczba operacji) danego rodzaju zadania (np. dodanie elementu na koniec listy) rośnie ze wzrostem rozmiaru zadania (czyli rozmiaru danych na wejściu, N
).
Jeśli masz O(n)
to znaczy, że w miarę jak rosną dane wejściowe (np. dodajesz coś na koniec coraz większej listy) rośnie czas obliczeń - w tym przypadku liniowo, bo przejście od początku do końca listy (by tam coś dodać) wymaga N
przejść.
Gdyby jakieś zadanie miało złożoność O(1)
(np. uzyskanie dostępu do elementu tablicy, a nie linked list) to by znaczyło, że czas rozwiązania zasadniczo nie zależy od rozmiaru danych
Złożoność O(logn)
(np. dla wyszukiwania binarnego) oznacza, że relacja między czasem obliczeń a rozmiarem zadania jest logarytmiczna. W przypadku wyszukiwania binarnego - ponieważ dzielisz coraz mniejsze połówki i połówki połówek etc. aż trafisz na szukany element lub zyskasz pewność, że go nie ma, to liczba kroków jest ograniczona do log(n)
.