minallo
(Lenek32)
5 Styczeń 2013 17:05
#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
(Johny)
5 Styczeń 2013 17:43
#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
nr47
(Sawyer47)
5 Styczeń 2013 17:52
#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
minallo
(Lenek32)
5 Styczeń 2013 17:55
#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
([alex])
5 Styczeń 2013 19:47
#5
Nadal to O(n^3), owszem nieco mniejsze współczynniki tej O()