[Algorytmy] Złożoność obliczeniowa


(Lenek32) #1

Mam napisać, jaka jest złożoność obliczeniowa tego fragmentu:

for i <-- 1 to n

     do for j <-- 1 to i

          do for k <-- 1 to i

                   do x <-- x+1

Problem w tym, że nie wiem, jak obliczyć złożoność obliczeniową.

Są trzy pętle, ten kod rozumiem, że:

pierwszy element ma indeks i, j oraz k, jeśli wykonamy znów ponownie, wtedy drugi element ma indeks i, j oraz k, i tak dalej do n.


(Johny) #2

Jeżeli są 3 pętle for to mamy do czynienia z z algorytmem O(n^3).

jest tak dlatego,że każdej następnej danej ilość operacji wzrasta 3 krotnie

O(1)=1

O(1,2)=8 2*2*2

O(1,2,3)=27 3*3*3

O(1,2,3,4)=4*4*4=64


(Sawyer47) #3

Patrząc na dwie wewnętrzne pętli, instrukcja x <-- x+1 wykona się i^2 razy. To wszystko natomiast zostanie wykonane n razy dla i od 1 do n. Czyli piękny wzorek z pomocą Wolfram|Alpha: http://www.wolframalpha.com/input/?i=sum+i%3D1…n++i**2


(Lenek32) #4

Dziękuję, a funkcja zmienna n wynosi n^3?

A gdyby było tak:

for i <-- 1 to n

     do for j <-- 1 to i

          do for k <-- 1 to j

                   do x <-- x+1

Zmieniło się tylko w trzeciej pętli od 1 do j. To jaką funkcję zmiennej n ma?


([alex]) #5

Nadal to O(n^3), owszem nieco mniejsze współczynniki tej O()