Paaiškinkite laiko sudėtingumo O(n) koncepciją ir kokiose situacijose ji taikoma.

Laiko sudėtingumas O(n) reiškia, kad algoritmo vykdymo laikas tiesiškai auga su įvesties duomenų dydžiu n.

Tai reiškia, kad jei duomenų rinkinio elementų skaičius padvigubėja, vykdymo laikas maždaug taip pat padvigubėja.

Pavyzdys situacijos su O(n):

• Elemento paieška ne surūšiuotame masyve peržiūrint visus elementus.

• Visų skaičių sumos skaičiavimas sąraše.

Pavyzdys Swift:

func sumArray(_ array: [Int]) -> Int {
    var sum = 0
    for num in array {
        sum += num
    }
    return sum
}

Čia funkcija pereina per visus masyvo elementus vieną kartą, todėl jos laiko sudėtingumas yra O(n).