这个算法的时间复杂度是多少？

Question

public static void Comp(int n)
{
    int count=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=1;k<n;k*=2)
            {
                count++;
            }
        }
    }
    System.out.println(count);
}

有谁知道时间复杂度是多少？

什么是Big Oh()

你能一步步给我解释一下吗？

Answer 1

时间复杂度为O(n^2 log n)。为什么？每个 for 循环都是 n 的函数。而且你必须为每个 for 循环乘以 n；除了增长为 log n 的内部循环。为什么？对于每次迭代，k 都乘以 2。想想归并排序或二叉搜索树。

详情

对于前两个循环：从 0 到 n 的 1 求和，即 n+1，因此前两个循环给出 (n+1)*(n+1)= n^2+2n+1= O(n^2)

对于第 k 个循环，我们让 k 增长为 1,2,4,8,16,32,... 因此 2^k = n。取两边的log，得到k=log n

再次，不清楚？

所以如果我们设置 m=0 和 a=2 那么我们会得到 -2^n/-1 为什么 a=2？因为这是系列产生 2,4,8,16,...2^k

的值

Answer 2

理论上这是O(n^2 * log(n))。

两个外循环都是O(n)，内循环是O(log(n))，因为n的log base 2是你要除的次数n 通过 2 得到 1.

这也是一个严格的界限，即代码也是Θ(n^2 * log(n))

Answer 3

给你这个问题的人几乎肯定是在寻找答案n^2 log(n)，原因已由其他人解释。

然而这个问题真的没有任何意义。如果n > 2^30，k会溢出，使内循环无限。

即使我们将此问题完全视为理论问题，并假设 n、k 和 count 不是 Java int，但是一些理论上的整数类型，答案 n^2 log n 假设操作 ++ 和 *= 具有恒定的时间复杂度，无论需要多少位来表示整数。这个假设不是真的有效。

更新

有人在下面的评论中向我指出，根据硬件的工作方式，合理地假设 ++、*=2 和 < 都具有常数时间复杂度，无论需要多少位。这使我的回答的第三段无效。

这个算法的时间复杂度是多少？

What is the time complexity for this algorithm?

java

algorithm

time

complexity-theory

更新