Big-O嵌套while循环

Question

i <-- 1
while(i < n)
   j <--1
   while(j < i)
      j <-- j * 2
   i <-- i + 1
done

我对此的镜头将是O(log n)内循环.而且我猜测外环是O(n)一个整体的复杂性O(n log n).确认？

Answer 1

您可以使用Sigma表示法逐步正式进行,以获得确切的迭代次数 - 查看Discrete Loops和Worst Case Performance文章(第10页).

结果经验证实.

Answer 2

是的，你是对的，但要正确地弄清楚它并不那么简单:)。

内循环很简单log n，无需进一步解释。

然而外循环并不那么简单，因为在每个循环中它都会改变内循环的执行时间。

如果您考虑一下，内部循环将运行（随着i增加）：

log 1 + log 2 + log 3 + log 4 + log 5 .... + log n

由于一些对数定律，它与log (1*2*3*4*....*n)which相同

log (n!)

有一个定律n!具有相同的复杂性（注意，它是复杂性，它在代数中是不同的）n^n

所以log (n!) = O(log (n^n))

现在我们可以切换回代数，因为log (n^k) = k*log (n)我们得到了结果

log (n^n)=n log n

结果 ：

时间复杂度为O(n log n)