Big O Theory-三重嵌套循环

Question

如果我有以下功能:

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？

Answer 1

您的函数是O(1)因为它返回第一个k，循环在第一次迭代时结束。假设它不立即返回，则如您所想，它是n^5。

\n\n

\xe2\x80\x8b\xe2\x80\x8b\n对于每个 i，第二个循环是循环i^2次数，第三个循环是持续j次数。\n所以对于每个i它都是循环i^4次数。所以总数Sum(i^4) (1..n)是O(n^5)。

\n