java - 以下代码段的时间复杂度是多少？

Question

对于下面的代码段，以 big-oh 表示法估计时间复杂度。

for (int i=0; i< n; i++)

for (int j=0; j*j <n;j++)

for (int k=0; k < n/2;k++)
    System.out.println (i+j+k);

我认为它们是嵌套循环，但我不是 100% 确定。据我所知，第一个循环的最差时间是 O(n)，第二个循环是 O(sqrt(n))，第三个循环是 O(log n)。那是对的吗？我是否只需将这些值相乘即可获得整个循环的时间复杂度？

Answer 1

为了扩展 Krypton 的评论，循环如下:

• 循环 1:O(n)，正如您提到的
• 循环 2:正如您提到的，O(sqrt(n)) == O(n^(1/2))。
• 循环 3:O(n/2)，去除常数因子后为 O(n)。

相乘，循环 1 和 3 一起是 O(n^2)，三个一起是 O(n^(5/2)) 或 O(n^(2.5))。这是二次时间和多项式时间之间的一些奇怪的灰色区域。