Co to jest analiza Big O tego algorytmu?

Question

pracuję na kursie struktur danych i nie jestem pewien, jak postępować w/Big tej analizy O:

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++; 

Mój początkowy pomysł, że jest to O (n^3) po redukcji, ponieważ najbardziej wewnętrzna pętla działa tylko wtedy, gdy j/i nie ma reszty, a reguła mnożenia nie ma zastosowania. Czy moje rozumowanie jest tutaj poprawne?

Answer 1

Zignorujmy tutaj zewnętrzną pętlę na sekundę, a następnie przeanalizujmy ją pod kątem i.

W połowie pętli biegnie i^2 razy, a powołuje wewnętrzną pętlę ilekroć j%i == 0 oznacza to, że go uruchomić na i, 2i, 3i, ...,i^2, a przy każdym uruchomieniu aż odpowiedniej j, oznacza to, że wewnętrzna podsumowanie pętla czasu pracy jest :

i + 2i + 3i + ... + (i-1)*i = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2] 

Ostatnia równość pochodzi z sum of arithmetic progression.
Powyższe informacje znajdują się w O(i^3).

powtarzać to do zewnętrznej pętli, która biegnie od 1 do n a dostaniesz czas O(n^4) uruchomiony, ponieważ trzeba rzeczywiście:

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 sum of cubes
A powyżej jest w , która jest twoją złożonością.