O（n ^ 2）来自O（n ^ 2 * log n）？(Where O(n^2) comes from in O(n^2 * log n)?)

O（n ^ 2）来自O（n ^ 2 * log n）？(Where O(n^2) comes from in O(n^2 * log n)?)

你能解释一下O（n ^ 2 * log n）的样子吗？ 我明白了O（n * log n） ：

s=0 for(i=0; i<n; i++) { for (j=1; j<n; j *= 2) { s=s+i*j; } s=s+1 }

当外循环从1运行到n是O（n）并且内循环每个外循环重复log（n）次，例如j * = 2.此外，我确实理解O（n ^ 2）的作用（性能与输入数据大小的平方例如）

s=0 for(i=0; i<n; i++) { for (j=0; j<n; j++) { s=s+i*j; } s=s+1 }

但是什么是O（n ^ 2 * log n） ？ 你能举个例子吗？

Can you please explain what O(n^2 * log n) can look like? I do understand O(n * log n) :

s=0 for(i=0; i<n; i++) { for (j=1; j<n; j *= 2) { s=s+i*j; } s=s+1 }

when outer loop runs from 1 to n is O(n) and the inner loop repeats log(n) times per outer loop e.g j *= 2. Also I do understand what O(n^2) does (performance is directly proportional to the square of the size of the input data e.g)

s=0 for(i=0; i<n; i++) { for (j=0; j<n; j++) { s=s+i*j; } s=s+1 }

but what is O(n^2 * log n)? Can you please give an example.

最满意答案

你只需要在外面添加一个for循环。 这使得O（n ^ 2 * log n）因为你重复O（n * log n） n次 。

for(int k=0; k<n; k++) { s=0 for(i=0; i<n; i++) { for (j=0; j<n; j *= 2) { s=s+i*j; } s=s+1 } }

You only need to add one for loop on the outside. That makes it O(n^2 * log n) because you repeat O(n * log n) n-times.

for(int k=0; k<n; k++) { s=0 for(i=0; i<n; i++) { for (j=0; j<n; j *= 2) { s=s+i*j; } s=s+1 } }