pętla zadanie na analize Opcje

[karis]

mozecie mi wytlumaczyc jak to zrobic?:

Kod

for I=1 to n do
    for J=I to n do
        Op(I, J);
    end for;
end for;

ile razy jest wykonywana ta petla?

uogolnij wzor na petle glebokosci 3

[Jabol]

To proste. Liczba operacji tej pętli to
Liczba operacji(Twoja funkcja) = \sum\limits_{i=1}^n\sum\limits_{j=i}^n 1 = \sum\limits_{i=1}^n n-i+1 = 1 + 2 + 3 + 4 + ... + n = n(n+1)/2

Proste, wystarczy znać wzór na sumę ciągu arytmetycznego. Kiedy teraz tego uczą, chyba jeszcze w gimnazjum co? Trzeba troszkę do podstaw wrócić.

Co oznacza, że rzeczywiście Ilość operacji(Twoja funkcja) \in O(n^2)

Ten post edytował Jabol 1.11.2011, 19:58:50