[kowalzmetina]

Mam pytanko. Muszę oszacować złożoność obliczeniową
np. jest funkcja z pętlą while która leci po elementach listy jednokierunkowej. gdy znajdzie jakiś element pasujący do warunku z if-a zwraca dany element.
Czy to będzie złożoność liniowa : o(n) ?
#studbaza #programowanie

[SwordPL]

@kowalzmetina:
Tak, bo pesymistycznie ostatni element będzie tym spełniającym predykat.

[zakopiak]

@kowalzmetina: Tak, zakładając, że złożoność obliczeniowa zawarta wewnątrz while'a jest równa O(1).

[kowalzmetina]

@SwordPL: @zakopiak: ok dzięki

[N.....a]

nie masz na myśli O(n)? o(n) i O(n) to dwie inne rzeczy.
https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu#Notacja_„małe_o”
ten przykład to O(n), bo w pesymistycznym przypadku przeleci n elementów
o(n) to chyba nie jest

[T.....y]

@kowalzmetina: niby tak, a jednak czasem nie
zdarzają się pętle, których zakres sprawia, że z o(n) robi ci sie o(logn), ale rozumiem, że miałeś na myśli, że w pesymistycznym przypadku leci po wszystkich elementach listy

[s.....a]

@SwordPL: pesymistycznie to żaden element nie spełni predykatu więc pesymistyczny przypadek jest znacznie częstszy niż się wydaje

[SwordPL]

@sakfa: Dobra uwaga.

@kowalzmetina: W sumie istotną różnicą jest o i O (plus jeszcze omega, Omega i Theta).

Złożoność Omega(n) można nazwać best-scenario case.
Złożoność Theta(n) można nazwać average-scenario case.
Złożoność O(n) to worst-scenario case.

Na przykład quicksort jest Theta(nlogn), a O(n^2), zaś merge sort jest Theta(nlogn) i O(nlogn).

Teraz tak, różnica między little-o, a big-O tkwi w tym, że funkcja złożoności dla big-O może być tego

[N.....a]

@leoha: "every function that is little-o of g is also big-O of g, but not every function that is big-O of g is also little-o of g (for instance g itself is not, unless it is identically zero near ∞)."

odwrotnie

notacja małego "o" znaczy mniej więcej "rośnie wolniej niż". Dużego "O" znaczy "rośnie tak samo lub wolniej"

[leoha]

odwrotnie

@Niekompilka: tak wiem, zorientowałem się po fakcie :)

[alex-fortune]

@kowalzmetina: worst case O(n)

[cevilo]

@kowalzmetina: przecież to wszystko zależy co jest w ifie, a jeśli w ifie te n elementów przegląda się jeszcze w zagnieżdżonej pętli, to robi się np n2, cokolwiek