你能解释一下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 } }更多推荐
发布评论