Veri yapıları ders çalışıyorum ve w/ Büyük O analize devam etmek için nasıl emin değilim:

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  ;

Benim ilk fikir bu O(n^3) sonra azalma, çünkü içteki döngü sadece çalıştırmak j/i yok kalan ve çarpma kuralı uygulanamaz. Benim akıl doğru burada mı?

Hadi bir an için dış döngü burada göz ardı, ve bırak i açısından analiz eder.

Orta döngü çalışır i^2 kat ve yürütmesini iç döngü ne zaman j%i == 0 demek çalıştırın i, 2i, 3i, ...,i^2 ve de her zaman çalıştırmak kadar ilgili j, iç döngü toplam süre:

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

Son eşitlik sum of arithmetic progressiongeliyor.
Yukarıdaki O(i^3).

n 13 *uzanan dış döngü için bu işlemi tekrarlayın ve gerçekten beri O(n^4), zaman koşma olacak:

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)

Son denklemi sum of cubesgeliyor
Ve yukarıdaO(n^4)senin karmaşıklığı.