W ostatnim poście napisałem na końcu, że mój algorytm jest O(n^2). Co to właściwie oznacza?

Problem złożoności obliczeniowej to pytanie “Jak długo mój algorytm będzie działał?”

Najprostsza odpowiedź jest “To zależy”. Ale od czego?

Algorytm działający w czasie stałym

Algorytm wykonywany jest w czasie stałym, czyli niezależnie od jego parametrów, będzie zawsze wykonywał co najwyżej P kroków. P jest dla danego algorytmu jakąś stałą. Powiemy o takim algorytmie, że jest O(1).

Przykład:

let suma a b = a + b
let head list =
    match list with
    | [] -> None
    | h::_ -> Some h

Algorytm działający w czasie liniowym

Algorytm działa w czasie liniowym względem jakiegoś jego parametru. Np. algorytm przetwarzający listę wykona tyle kroków ile jest elementów w tej liście. Będzie liniowo zależeć od długości tej listy. Innym przykładem jest algorytm liczący n-tą liczbę Fibonacciego. Im większe n tym dłużej będzie liczył, proporcjonalnie. 2 razy większe n, 2 razy dłużej liczy. Taki algorytm jest O(n).

let suma lista =
    match lista with
    | [] -> 0
    | h::t -> h + (suma t)
let fib n =
    if n < 2 then 1
    else
        let rec fibpom prev1 prev2 i =
            if i = 0 then prev1
            else fibpom (prev1 + prev2) prev1 (i-1)
        fibpom 2 1 (n-2)

Algorytm działający w czasie logarytmicznym

Mając do czynienia ze strukturą słownikową, np. drzewem BST, jesteśmy w stanie wyszukać element szybciej niż w czasie liniowym, t.j. przeglądając wszystkie elementy po kolei. W BST mamy posortowane elementy i patrzymy czy to czego szukamy jest większe czy mniejsze od elementu po środku (chyba, że nim jest). I następnie powtarzamy ten algorytm dla połowy elementów. Dzieląc na pół kilkukrotnie dojdziemy do szukanego elementu (lub nie jeśli go nie ma). Okazuje się, że maksymalnie możemy wykonać to dzielenie na pół “logarytm przy podstawie 2 z n” razy. Więc ten algorytm jest O(log n).

let find x (array :int array) =
    let rec findpom start stop =
        if stop < start then false
        else
            let middle = (start + stop) / 2
            if array.[middle] = x then true
            else if x < array.[middle] then findpom start (middle - 1)
            else findpom (middle + 1) stop
        findpom 0 (array.Length - 1)

Bardziej złożone algorytmy

Większość algorytmów o złożoności wielomianowej to złożenia algorytmów liniowych i logarytmicznych. Np. algorytm O(n^2) to algorytm gdzie dla każdego elementu listy przeglądamy całą listę.

Są też algorytmy wykładnicze O(c^n). Te zajmują bardzo dużo czasu. Przykładem takiego algorytmu jest backtracking.

Big O

To duże O, które widzimy przy określaniu złożoności obliczeniowej to skrót zapisu

algorytm(n) ≤ g(n)∙c ⟷ algorytm(n) = O(g(n))

Więcej o tym znajdziecie na Wikipedii.