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 and Worst Case Performance纸(第 10 页)。



结果得到了实验验证。