嵌套循环的渐近分析

Question

我想更好地理解渐近分析，因为我相信我对此没有深入的了解。如果有人可以强调一种更好的方法，我将不胜感激。这里有两个例子

for (int i = 1; i <= n; i *= 2) { for (int j = 0; j < n; j++) { count++; } }

这道题来自测验，答案是 O(n log n)

我看了斯坦福大学的一个讲座，例子如下

for i = 1 to n
  for j = i + 1 to n
   if A[i] == A [j] return TRUE otherwise
   return FALSE

第二个给定问题的渐近分析是二次 O(n^2)

我怎么知道什么时候 O(n log n) 或 O(n^2) 它们都嵌套了 for 循环？

非常感谢任何回答。预先感谢

Answer 1

第一个示例是 O(nlogn) 因为外循环重复 log(n) 次，并且它的每次重复都需要内循环重复 O(n) 次 - 所以总共 [=13] =].

但是，在第二个示例中 - 外循环需要 O(n) 次迭代，并且对于每次迭代 i - 它需要内循环的 O(n-i) 次迭代。这意味着总共需要 n + (n-1) + (n-2) + ... + 2 + 1 时间。这是等差级数，其和在O(n^2)

如果不了解所发生的某些事情，就无法 "easy way" 了解复杂性 - 复杂性分析视具体情况而定。
但是，有一些提示可能对您有所帮助，例如 - 如果迭代计数器乘以每次迭代 - 这强烈表明复杂度函数中将涉及对数，就像您的第一个示例一样。

Asymptotic Analysis for nested loop