Złożoność obliczeniowa algorytmu - problem

0

Witam,

mam takie polecenie aby podać jaka jest złożoność obliczeniowa następującego fragmentu kodu programu (dokładna) i podać klasę O

fragment:

for i:=1 to n do
   for j:=i+1 to n do
   x = x+1;

 

I tu moja prośba o wytłumaczenie jak się liczy tą złożoność. Wynik jest taki że złożoność wynosi n2/2 -n/2

0

Musisz po prostu policzyć ile racji wykonuje się operacja x=x+1
Liczmy więc:
dla i=1 mamy n-1 (tyle razy obróci sie wewnętrzna pętla, bo będzie lecieć od j=2 do n, więc n-1 razy)
dla i=2 mamy n-2
...
dla i=n-1 mamy 1
dla i=n mamy 0
W sumie mamy więc:
0 + 1 + 2 + 3 + ... + (n-2) + (n-1)
co jest ciągiem arytmetycznym o różnicy 1
Suma takiego ciągu, jak wie każde dziecko w 3 klasie podstawówki, to
n/2 * ((n-1) + 0) = (n^2)/2 - n/2

0

No właśnie i w tym problem bo tak:

Jeżeli i=1 to n-1, tyle że za cholerę nie wiem dlaczego, bo przecież nie przyjmuje żadnego n, a właśnie od n zależy ile razy się wykona.

0

Rozumiem ze w 2 klasie podstawówki przegapiłeś taki temat jak równania z jedną niewiadomą? Przecież wszystko co tu liczymy zalezy od N i nie musimy go wcale znać.
Skoro i=1 to pętla będzie się powtarzać dla każdej liczby całkowitej j od 2 do n. Ile jest liczb całkowitych pomiędzy 2 i n? Jeśli nie wiesz, to myślę że powinieneś szybko zmieniać studia, bo informatyka nie jest dla ciebie i nie warto żebyś tracił czas. Otóż liczb całkowitych pomiędzy 2 i n jest oczywiście n-1. Nie wierzysz? No to dowód przez przykład (:P):
załóżmy n = 7 mamy:
2,3,4,5,6,7 i liczb jest 6= 7 -1, czyli n-1
załóżmy n = 10
2,3,4,5,6,7,8,9,10 i liczb jest 9 = 10-1, czyli znów n-1

0

Przyznaje ze z matmy nigdy dobry nie byłem :P ale takie podstawy znam, tylko cały czas myślałem o tym n i dlatego mnie to myliło.

Wielkie dzięki za pomoc, teraz już rozumiem :)

Pozdrawiam ! :)

0
Shalom napisał(a)

dowód przez przykład (:P):
załóżmy n = 7 mamy:
2,3,4,5,6,7 i liczb jest 6= 7 -1, czyli n-1
załóżmy n = 10
2,3,4,5,6,7,8,9,10 i liczb jest 9 = 10-1, czyli znów n-1

no i to się nazywa dowód! a nie jakieś tam indukcje, wprost i inne duperele. Zabrakło tylko "q.e.d."

1 użytkowników online, w tym zalogowanych: 0, gości: 1