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)

Answer 2

(a) 你的分析是正确的

(b) 外循环进行 log(N) 次。内部循环按1, 2, 4, 8, ...log(N) 次的顺序进行，这是一个几何级数，等于(approx) O(2^log(N))或两倍于最高倍数。

例如：1 + 2 + 4 = (approx)2*4，1 + 2 + 4 + 8 = (approx)2*8。

因此总复杂度为O(2^log(N)) = O(N)

(c) 这与 (b) 顺序相反

Answer 3

精细时间复杂度

I=1;
K=1;
While(k<n)
{
    Stmt;
    K=k+i;
    I++;
}