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

[slontrabalski]

n^2

[karis]

na pewno nie

ma wyjsc n(n+1)/2

[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

[peter13135]

zauważcie że licznik drugiej pętli zaczyna się od j a nie 1.

[1010]

zauważcie że licznik drugiej pętli zaczyna się od j a nie 1.

Jak już to od i

[croc]

Nie, to nie jest bez sensu. Tylko w ten sposób osiągniesz prosto "schodkową" progresję.

[Niktoś]

Usunąłem, posta ,trochę za szybko to stwierdziłem.
Z każdym wykonaniem pierwszej pętli, liczba operacji drugiej pętli jest zmniejszana.

zauważcie że licznik drugiej pętli zaczyna się od j a nie 1

-tak ale zaczyna się od 1-przy drugim cyklu pierwszej pętli,J=2 ,przy trzecim j=3 itd.

ile razy jest wykonywana ta petla?

Trochę nieprecyzyjne pytanie-o którą pętle chodzi-bo jeśli chodzi o pierwszą to n razy.



Ten post edytował Niktoś 5.11.2011, 13:15:05