Witam,
mam do napisania program, który mam mieć liniową złożoność w zależności od ilosci elementow tablicy. Program ma wypisywać TAK lub NIE na wyjściu, czasem muszę przelecieć całą tablice żeby wypisać odpowiedni komunikat na wyjściu (i wtedy wiem że złożoność jest na pewno liniowa), ale czasem mogę to stwierdzić jakie ma być wyjście już po sprawdzeniu pierwszych dwóch elementów. Czy sprawdzenie tylko dwóch pierwszych w szczególnym przypadku i natychmiastowe wypisanie wyjścia oraz zakończenie programu psuje złożoność liniową algorytmu?
0
0
Z reguły podaje się przypadek średni/pesymistyczny. Optymistycznie to bardzo dużo algorytmów ma O(1) bo akurat się trafi że od razu znamy odpowiedź ;)
W twoim przypadku absolutnie nic się nie "psuje". Zresztą im niższa złożonośc tym lepiej, więc gdyby twój algorytm miał średnio O(1) a nie O(n) to by znaczyło ze go coś "poprawia" a nie "psuje".
0
tak, wiem że to jest lepiej niż gdyby zawsze przelatywał całą tablicę. W pesymistycznym przypadku przelatuje mi tylko całą tablicę jeden raz. Ale prowadzący powiedział wyraźnie, algorytm ma mieć złożoność O(n), a nie inną. Więc stąd moje wątpliwości, bo czasem mogę stwierdzić jakie będzie wyjście będąc w różnym elemencie tablicy
0
Domyślnie zawsze podaje się złożoność pesymistyczną. Dlatego np dla sortowania przez wstawianie podaje się złożoność pesymistyczną O(n^2), a nie optymistyczną O(n). Jeśli ktoś podaje/ chce złożoność inną niż pesymistyczna to musi to wyraźnie podać.
Druga sprawa to to, że O(n) to zbiór funkcji, które są asymptotycznie nie większe od funkcji f(x) = x. Funkcja f(x) = 1 się do nich zalicza. Inaczej mówiąc, zbiór O(1) zawiera się w zbiorze O(n). Funkcja f(x) = c, gdzie c to stała, należy do obydwu tych zbiorów. Poczytaj sobie o złożonościach na Wikipedii.
0
O(n) to oszacowanie górne. omega(n) to oszacowanie dolne. Co znaczy, że m a być dokładnie O(n)? Może chodzi o theta(n)?