big-o - 关于 O(n^2logn)

Question

void function(int n ) {
    int i, j , k ;
    for ( i = n/2 ; i <= n ; i ++) 
        for ( j = 1; j + n/2 <= n; j++ ) 
            for ( k = 1; k <=n ; k = k*2 )
                count ++;
}

外部循环执行 n/2 次，中间循环执行 n/2 次，内部 llop 执行 logn 时间。

上述函数的复杂度是 O(n^2logn)，但是 n/2 和 n/2 将如何变为 n^2 呢？

谢谢

Answer 1

您的算法的确切迭代次数及其增长复杂度的顺序将按如下方式推断：

支持文件：这里

Answer 2

循环是嵌套的，因此它们的所有计数都会相乘。(n/2) * (n/2) 是 n^2 / 4，但常数对 big-O 无关紧要；n^2 / 4 = O(n^2) 并且这样写。

Answer 3

对于大 O 表示法，省略了常数：“如果 f(x) 是多个因子的乘积，则省略任何常数（乘积中不依赖于 x 的项）。”

所以你的内循环是 logn，你的中间和外循环是 n/2，但一起是 (n/2) * (n/2) * logn = 1/4 (n^2logn)，1/4 被丢弃给出 O(n^2logn)。

参考： http ://en.wikipedia.org/wiki/Big_oh_notation