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

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

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

但是这个问题没有任何意义。如果n > 2^30 , k将溢出，使内部循环无限。

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

更新

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