Na czym polega analiza tego algorytmu?
Pracuję nad kursem struktur danych i nie wiem, jak postępować z tą wielką analizą:
sum = 0;
for(i = 1; i < n; i++)
for(j = 1; j < i*i; j++)
if(j % i == 0)
for(k = 0; k < j; k++)
sum++;
Moim początkowym pomysłem jest to, że jest to O (n^3) po redukcji, ponieważ najbardziej wewnętrzna pętla będzie działać tylko wtedy, gdy j
/i
nie ma reszty i zasada mnożenia nie ma zastosowania. Czy moje rozumowanie jest poprawne?
1 answers
Zignorujmy pętlę zewnętrzną na sekundę i przeanalizujmy ją w kategoriach i
.
Pętla Środkowa uruchamia się i^2
razy i wywołuje pętlę wewnętrzną za każdym razem, gdy j%i == 0
, to oznacza, że uruchamiasz ją na i, 2i, 3i, ...,i^2
, a za każdym razem uruchamiasz do odpowiedniego j
, oznacza to, że wewnętrzna pętla sumuje czas pracy:
i + 2i + 3i + ... + (i-1)*i = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2]
Ostatnia równość pochodzi z sumy progresji arytmetycznej.
powyższe znajduje się w O(i^3)
.
Powtórz to do zewnętrznej pętli który biegnie od 1
do n
i otrzymasz czas działania O(n^4)
, ponieważ faktycznie masz:
C*1^3 + C*2^3 + ... + C*(n-1)^3 = C*(1^3 + 2^3 + ... + (n-1)^3) =
= C/4 * (n^4 - 2n^3 + n^2)
Ostatnie równanie pochodzi z sumy sześcianów
a powyższe jest w O(n^4)
, co jest twoją złożonością.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-19 20:39:13