Dlaczego ten kod jest uważany za O (N^6) w notacji Big Oh?

Question

właśnie czyta another question i zaintrygował mnie ten kod:

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < i*i; j++) 
    { 
     for(k = 0; k < i*j; k++) 
     { 
      pseudo_inner_count++; 
      for(l = 0; l < 10; l++); 
     } 
    } 
} 

ja nie rozumiem, jak to może być O (N^6). Czy ktoś może mi to załatwić?

Answer 1

rzeczywistości to jest:

• Pętla i iteruje O (N) razy, więc wartość i jest O (N), więc możemy powiedzieć O (I) = O (N).
• Pętla j iteruje O (I^2) = O (N^2) razy (gdy rozpatrywany jest sam, bez zewnętrznej pętli).
• Pętla k iteruje O (I * J) = O (N * N^2) = O (N^3) razy.
• Pętla l po prostu się iteruje 10 razy, więc jest to O (1).

Pętle są zagnieżdżone, więc musimy je pomnożyć (czy rozumiesz dlaczego?). Suma to O (N) * O (N^2) * O (N^3) = O (N^6).

Answer 2

by powiedzieć:

• N dla pierwszej pętli
• n² do drugiej pętli => sumie n³
• n² do trzeciej pętli => łącznie n⁵
• kolejny n-pętli => sumie n⁶

Answer 3

To

n dla pierwszej pętli n² do drugiej pętli n³ do trzeciej pętli

Wewnętrzna pętla O (1)

Całkowita O (n⁶).

Powodem, dla którego trzecia pętla jest n³, jest ponieważ kiedy myślisz o tym, j osiąga n², a ja osiąga n, więc i * j osiąga n³.