Big O: Nested For Loop With Dependence

9

Dostałem zadanie domowe z Big O. Utknąłem z zagnieżdżonymi pętlami zależnymi od poprzedniej pętli. Oto zmieniona wersja mojego pytania do pracy domowej, ponieważ naprawdę chcę to zrozumieć:

sum = 0;
for (i = 0; i < n; i++ 
    for (j = 0; j < i; j++) 
        sum++;

Część, która mnie wyrzuca, to j < iczęść. Wygląda na to, że działałby prawie jak silnia, ale z dodatkiem. Wszelkie wskazówki będą mile widziane.

— Raphael
źródło

Ładne wyjaśnienie tutaj

— saadtaame,

10

Pozwólcie, że wyjaśnię kilka rzeczy, interesuje was notacja big-O - oznacza to górną granicę . Innymi słowy, można liczyć więcej kroków niż faktycznie. W szczególności możesz zmodyfikować algorytm do

 ...
    for (j = 0; j < n; j++) 
 ...

Tak więc dwa zagnieżdżonej pętli, z których każdy działa w pętli $n$ razy, co daje górna granica w $O(n^2)$

Oczywiście chciałbyś mieć dobre oszacowanie górnej granicy. Aby zakończyć, chcemy ustalić dolną granicę. Oznacza to, że można liczyć mniej kroków. Rozważ więc modyfikację

for (i = n/2; i < n; i++)
    for (j = 0; j < n/2; j++) 
        sum++;

Tutaj wykonujemy tylko niektóre z iteracji pętli. Ponownie mamy dwie zagnieżdżone pętle, ale tym razem mamy iteracji na pętlę, co pokazuje, że mamy co najmniej dodatków. W tym przypadku oznaczamy tę asymptotyczną dolną granicę . Ponieważ dolna i górna granica pokrywają się, możemy nawet powiedzieć, że jest ciasną asymptotyczną granicą i piszemy . $n/2$ $n^2/4$ $\Omega(n^2)$ $n^2$ $\Theta(n^2)$

Jeśli chcesz dowiedzieć się więcej, przeczytaj tutaj .

— A.Schulz
źródło

6

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++) 
        sum++;

Prześledźmy to:

Gdy i = 0, pętla wewnętrzna w ogóle nie będzie działać ( 0<0 == false).
Gdy i = 1, pętla wewnętrzna uruchomi się raz (dla j == 0).
Gdy i = 2, pętla wewnętrzna uruchomi się dwukrotnie. (dla j == 0 i j == 1).

Ten algorytm zwiększy zatem sumnastępującą liczbę razy:

\sum_{x = 1}^{n} x - 1 = 0 + 1 + 2 + 3 + 4... + n - 1 = \frac{n (n - 1)}{2}

$\sum_{x=1}^n x-1 = 0+1+2+3+4... + n-1 = \dfrac{n(n-1)}{2}$

Po inspekcji możemy zobaczyć, że suma jest „liczbą trójkątną”. Rozprowadzanie do końca licznika, otrzymujemy , przy czym najszybciej rośnie czas jest stąd Bachman, Landau, Big-theta złożoność . $n$ $\dfrac{n^2-n}{2}$ $n^2$ $\theta(n^2) \equiv O(n^2) \ and\ \Omega(n^2)$

— KeithS
źródło

3

zobaczmy, czy mogę to wyjaśnić ...

Więc jeśli wewnętrzna pętla to j

Teraz, dla pierwszej iteracji, wykonujesz n- (n-1) razy przez wewnętrzną pętlę. za drugim razem wykonasz n- (n-2) razy przez wewnętrzną pętlę. W N-tym czasie robisz n- (nn) razy, czyli n razy.

jeśli uśrednisz ile razy przejdziesz przez wewnętrzną pętlę, n / 2 razy.

Można więc powiedzieć, że to O (n * n / 2) = O (n ^ 2/2) = O (n ^ 2)

Czy to ma sens?

To trochę dziwne, ale myślę, że rozumiem! Dzięki! Haha może zająć trochę czasu

Więc jeśli ta j < iczęść rzeczywiście była j < i^2, to wynikowe O dla tej części wynosiłoby n ^ 2/2?

Przede wszystkim zauważ, że O (n ^ 2/2) = O (n ^ 2). Teraz, jeśli zmienisz to na j <i ^ 2, to robisz (n- (n-1)) ^ 2 przy pierwszej iteracji i n ^ 2 przy ostatniej iteracji. Nie pamiętam, co oznaczałoby duże O dla wewnętrznej pętli. O (n ^ 2) jest luźną górną granicą. Zatem luźna górna granica dla całej rzeczy to O (n ^ 3), ale ta wewnętrzna pętla jest mniejsza niż O (n ^ 2). Czy to ma sens?