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

Question

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

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。 p>

因此，步数总数的界限为:(n-1)/2 - log₃n，或更简单地表述为O(n) 。