Duża złożoność O - python-3.x, big-o

Próbuję zrozumieć Big O i myśl, że pomoc w prostym programie może pomóc.

def sum(n):
k = 0
j = 0
while k < n:
k = k + 1
while j < n:
j = j + 1
k = k + j
return k

k i j mają początkowo przypisaną wartość 0, któraliczy się na 2 przypisania, pierwsza pętla wykonuje 1 zadanie n razy, a druga wykonuje 2 przypisania n razy. Tak więc wyrażenie to 2 + n + 2n.

Ponieważ pierwsze dwie warunki w powyższymwyrażenie (2 i n) są stałe, staną się nieistotne w porównaniu z trzecim terminem, który mnoży n przez 2 jako n rośnie. Tak więc Big O dla kodu będzie O (2n).

Czy moja logika i odpowiedź są poprawne? Z góry dziękuję

Odpowiedzi:

Twoja odpowiedź jest poprawna, chociaż nie mówimy O (2n), ale Na) zamiast.

Co Na) oznacza to, że najgorszy przypadek złożoności twojego algorytmu zwiększa się najwyżej liniowo, czyli tak właśnie jest ostatecznie związany przez jakąś funkcję formularza a * n gdzie za jest trochę stały. Rzeczywista stała nie ma znaczenia dla zapisu big-O.

Aby być bardziej technicznym, mówię ostatecznie ponieważ mówimy o tym, co nazywamy ograniczającym zachowaniem twojego algorytmu, możesz myśleć o nim jako o opisie zachowania tylko dla bardzo dużych danych wejściowych.

Na przykład w twoim algorytmie, jako n rośnie, coraz mniej zależy nam na przypisaniach k = 0 i j = 0stają się znikome.

Podsumowując, notacja big-o ma na celu opisanie szybkość, z jaką wzrasta czas biegu, nie opisując dokładnie, czym jest czas wykonywania.