Powiedzmy, że mam taką funkcję i muszę oszacować jej złożoność, ale tylko ze względu na operację w linijce 7
I teraz nie wiem czy w takim przypadku nie wiem czy brać pod uwagę to, że pętla wcześniej linii 7 podnosi złożoność do f(n) = O(n^2), czy nie powinno się właśnie tego brać pod uwagę i za przyjąć, że f(n) = O(n), bo domyślam się, że pewnie to drugie podejście jest poprawne. Może mi ktoś powiedzieć czy dobrze kombinuje.
Jeszcze raz po polsku.
I teraz nie wiem czy w takim przypadku brać pod uwagę to, że pętla wcześniej linii 7 podnosi złożoność do f(n) = O(n^2), czy nie powinno się właśnie tego brać pod uwagę i przyjąć, że złożoność obliczeniowa algorytmu to f(n) = O(n), bo domyślam się, że pewnie to drugie podejście jest poprawne. Może mi ktoś powiedzieć czy dobrze kombinuje.
Na moje oko linijka siódma (suma - +1.) nic nie robi, ponieważ nie modyfikuje żadnej zmiennej.
A nawet, gdyby tam miało być suma += 1, w dalszym ciągu nie zmienia to złożoności obliczeniowej, ponieważ suma nie jest wykorzystywana jako iterator żadnej pętli (na przykład).
Twoja funkcja ma złożoność O(n^2), ponieważ składa się z dwóch pętli wykonujących n obliczeń każda - czyli n * n = n^2.
Edit: ma złożoność O(n^2) zakładając, że druga pętla miała mieć instrukcję krokową j++, a nie i++. W innym wypadku faktycznie O(n).
Analizuje się to w ten sposób:
Złożoność tego algorytmu to O(n^2) - bo dwie podwójne pętle zależne od n: n razy n operacji stałych.
A dokładnie operacji pojedynczych/stałych[1] (to jest niepewne bo zależy od sprzętu, implementacji i języka), jest:
Wiesław Akademicki napisał(a):
Powiedzmy, że mam taką funkcję i muszę oszacować jej złożoność, ale tylko ze względu na operację w linijce 7
I teraz nie wiem czy w takim przypadku nie wiem czy brać pod uwagę to, że pętla wcześniej linii 7 podnosi złożoność do f(n) = O(n^2), czy nie powinno się właśnie tego brać pod uwagę i za przyjąć, że f(n) = O(n), bo domyślam się, że pewnie to drugie podejście jest poprawne. Może mi ktoś powiedzieć czy dobrze kombinuje.
Wg mnie jest to O(n), bo operacją dominującą jest ta w linii 7.
Jeśli w linii 7 jest operator szacowania "+-" to należy go zapisać odwrotnie.
Wtedy rzeczywiście może wyjść że jest to operacja dominująca, ponieważ zwykle się nie powiedzie (suma będzie zwykle > 1), w związku z tym trzeba będzie dołożyć "%" żeby to zrozumieć.
Kiedy mówimy o szacowaniu złożonośc ze względu na operację, mamy na myśli typ operacji, a więc wszystkie występiania tej operacji (a nie tylko poszczególne "instancje"). W linijce 7 jest odejmowanie, ale bez przypisania do jakiejkolwiek zmiennej (być może to błąd i chodziło o -=). Więc złożoność tego algorytmu względem operacji arytmetycznych dodawania/odejmowania to nadal O(n^2). Linia 7 wykona się n razy, ale już linia 5 wykona się n^2 razy. Do tego skoro to dodawanie/odejmowanie uznaliśmy za dominujące to należy doliczyć inkrementację indeksów i, j.
Czy szacowanie złożoności tego algorytmu tylko ze względu na instrukcję z lini 7 ma jakiś sens? Wątpię, trzeba uwzględnić wszystkie operacje tego typu. Chyba, że ktoś mi wytłumaczy czemu dodawanie z linijki 7 dominuje nad dodawaniem z linijki 5, na tyle, by n lini 5 wykonywało się szybciej niż jedna instrukcja z linii 7.
PS.
W linii 4 jest błąd, inkrementuje się i zamiast j, w skutek czego wewnętrzna pętla nigdy się nie kończy.
Też nie zwróciłem uwagi, ale to pytanie było omyłkowe; szacowanie złożoności ze względu na operację nie odwołującą się do długości danych, nie ma sensu - bo to jest optymalizacja, a nie złozoność. Do złożoności dodaje to tylko banalny faktor: O(1).