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和<无论需要多少位，它们都具有恒定的时间复杂度。这使得我的答案的第三段无效。