Z definicji bardziej teoretycznej złożoność jest to określenie ilości zasobów potrzebnych do wykonania jakiejś operacji.
W przypadku pisania programów zazwyczaj zależy nam na czasie wykonania, lub potrzebnej pamięci.
Dla obecnych komputerów wykonanie tysiąca lub miliona operacji nie robi praktycznie żadnej różnicy.
Dla algorytmów(które poznała Ie^^) istnieje określona złożoność czasowa, czyli określenie jak zależy czas wykonania od
danych wejściowych. Złożoność pamięciowa(dla nas) na razie nie jest problemem.
Ilości i czasu trwania wykonanych operacji(dla określonych danych)nie da się jednoznacznie określić: na jednym zestawie komputerowym dany program będzie działał szybciej, na innym wolniej(zależy np. od procesora). Natomiast możemy powiedzieć
jak się te wartości zmienią w przypadku zmiany danych wejściowych na zasadzie porównania.
Notacja dużego O oznacza jak długo program się będzie wykonywał w najgorszym przypadku.
Najczęściej występujące notacje:
O(1): program się wykonuje w czasie stałym, niezależnie od danych wejściowych. Przykłady: znany program "Hello World",
zapisywanie liczby do tablicy, mnożenie dwóch liczb też traktujemy jako jedną instrukcję.
O(log n): program się wykonuje w czasie zależnym od rozmiaru danych wejściowych. Przykładowo program zamieniający
liczbę z systemu dziesiętnego na dwójkowy (nie, to nie tak - LD)
O(n): program się wykonuje w czasie liniowo zależnym od ilości danych wejściowych. Przykład: sumowanie liczb w tablicy.
O(n2): program się wykonuje w czasie zależnym od kwadratu ilości danych wejściowych (jeśli zwiększymy ilość
danych trzykrotnie, to program się będzie wykonywać 9 razy dłużej).
O(n3): na podobnej zasadzie jak wyżej.
O(2n): czas wykonania bardzo szybko rośnie przy zwiększaniu ilości danych źródłowych.
O(n!): jak wyżej(tylko jeszcze gorzej).
Jako przykłady podałem tylko omówione na lekcjach algorytmy.
