Próbuję dowiedzieć się złożoność czasową tego Pseudokod dany algorytm:Czas Złożoność algorytmu (zagnieżdżonych pętli)
sum = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n/6; j++)
sum = sum + 1;
wiem, że pierwsza linia biegnie
n razy
Ale nie jestem pewien co do drugiej linii.
Tu masz prosty podwójną pętlę:
for i=1;i<=n;i++
for j=1; j<=n/6; j++
więc jeśli policzyć, ile razy ciało pętli zostanie wykonany (czyli ile razy ta linia kodu sum = sum + 1; zostanie wykonany), ty zobaczy to:
n * n/6 = n²/6
które pod względem zapisu-o jest duża:
O (n²)
bo nie troszczą się o stałym terminie, bo jak n rośnie, stały termin sprawia, że nie ma różnicy (duży), jeśli jest tam, czy nie!
Kiedy i tylko gdy w pełni uświadomić sobie to, co mówię, można głębiej z tym miłym pytaniem: Big O, how do you calculate/approximate it?
Należy jednak zauważyć, że takie pytania są bardziej odpowiednie dla Theoretical Computer Science, a nie SO.
Wykonujesz operacje n * n/6, a więc złożoność czasu wynosi O (n^2/6) = O (n^2).
Dokładniej, 'n * (n/6)' operacje: złożoność jest taka sama, ale wynik jest różny. – chqrlie
Stosując notację Sigma, możemy znaleźć asymptotycznej granice swojego algorytmu w następujący sposób:
złożoność czasowa = suma? :) (n * n/6) –
Czy to nie byłby po prostu O (n^2)? Wydaje się proste. – Aede
To nie zawsze musi być trudne :) –