大 O 理论 - 三重嵌套循环

Question

6

If I have a function of:

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

这个函数的 big O 是否为 n^5，因为它有： n*((n-1)^2)*((n-1)^2)-1 ?

- Danny2036

如果您遍历所有k值，则其时间复杂度为O(n^3)。 - Shep

1

你能接受这个答案吗？ - kkdas02

可能是此for循环的大O分析的重复问题。 - Mohamed Ennahdi El Idrissi

2个回答

1

正式地，使用Σ符号表示法，您可以通过以下方式推断增长的阶:

enter image description here

- Mohamed Ennahdi El Idrissi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fastcodejava · Accepted Answer

你的函数的时间复杂度为O(1)，因为它在第一次迭代时就返回了第一个k。假设它不会立即返回，则像你想象的那样，它将是n^5。

对于每个i，第二个循环循环次，第三个循环走次。因此，对于每个，它循环次。因此总计是 Sum(i^4) (1..n)，其为O(n^5)。