c - 寻找时间复杂度

Question

我试图理解复杂性的细微差别以下每个示例。

例子A

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for (int j = 0; j < N; j++)
      sum++;

我的分析:

第一个 for 循环执行 lg n 次。
内循环独立于外循环，每次外循环执行N次。

所以复杂度一定是:
n+n+n...lg n次

因此复杂度为n lg n。

这是正确的吗？

例子B

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for(int j = 0; j < i; j++)
      sum++;

我的分析:

第一个 for 循环执行 lg n 次。
内循环的执行依赖于外循环。

那么当内循环执行次数不依赖于外循环时，我该如何计算复杂度呢？

示例 C

int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;

我认为示例 C 和示例 B 必须具有相同的复杂性，因为内部循环执行的次数不依赖于外部循环。

这是正确的吗？

Answer 1

在示例 B 和 C 中，内部循环执行了 1 + 2 + ... + n/2 + n 次。这个序列中恰好有 lg n 项，这确实意味着 int i = 0 执行了 lg n 次，但是总和为内部循环中的语句是 2n。所以我们得到 O(n + lg n) = O(n)