c - 如何计算算法的运行时间？

Question

我目前正在学习 Big O Notation 运行时间。我尝试计算一些代码的时间复杂度:

int i = 1;
int n = 3;  //this variable is unknown
int j;

while (i<=n)
{
    for (j = 1; j < i; j++)
        printf_s("*");
    j *= 2;
    i *= 3;
}

我认为这段代码的复杂度是 О(log n)。但即使它是正确的，我也无法解释原因。

Answer 1

时间复杂度不是 O(log n)，而是O(n)。

我们可以用结构化的方式计算。首先我们检查内部循环:

for (j = 1; j < i; j++)
    printf_s("*");

这里 j 从 1 迭代到 i。所以这意味着对于给定的 i，它将采取 i-1 步。

现在我们可以看看外循环，我们可以抽象出内循环:

while (i<=n)
{
    // ... i-1 steps ...
    j *= 2;
    i *= 3;
}

因此 while 循环的每次迭代，我们执行 i-1 步骤。此外，每次迭代 i 都会加倍，直到它大于 n。因此我们可以说这个算法的步数是:

log3 n
---
\       k
/      3  - 1
---
k=0

我们在这里使用 k 作为一个额外的变量，它从 0 开始并且每次递增。因此它会计算我们执行了多少次 while 循环体。它会在 3^k > n 时结束，因此我们将迭代 log₃(n) 次，每次迭代内循环都会重新开始3^k-1 步。

上面的总和相当于:

          log3 n
           ---
           \       k
-log3 n +  /      3
           ---
           k=0

上面是一个geometric series [wiki] ，等于:(1-3^log₃n)/(1-3)，或者简化，等于< em>(n^log₃3-1)/2，因此 (n-1)/2。

因此，总步数受限于:(n-1)/2 - log₃n，或者更简单地表述为 O(n) .