c - 以下相关循环的时间复杂度是多少？

Question

我有一个问题需要在本周的考试前得到解答。

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

我有这些依赖循环，我计算出外循环的大 O 为 O(logn)。

对于外部循环的每次迭代，内部循环从 1 到 i - 1， 我遇到的问题是我不知道如何计算内部循环的时间复杂度，然后计算整体复杂度(我习惯于将两个复杂度相乘，但我不确定这个)

非常感谢!

P.S:我知道 j *= 2 不会影响 for 循环。

Answer 1

正如您所认识到的，计算循环嵌套的复杂性(其中内部循环的边界因外部循环的不同迭代而变化)并不像两个迭代计数的简单相乘那么容易。您需要更深入地研究才能获得尽可能严格的界限。

这个问题可以被理解为询问内部循环体被执行了多少次，作为n的函数。在第一次外循环迭代中，i 为 1，因此 j 永远不会小于 i，因此不存在内循环迭代。接下来，i 是 3，因此有两次内循环迭代，然后下一次是 8 次，然后是 26 ... 简而言之，3^i-1 - 1 次内循环迭代。您需要将所有这些相加才能计算总体复杂性。

嗯，这个总和是 Σ_{i = 1, Floor(log n)} (3^i-1 - 1)，所以你可以说循环嵌套的复杂度是

    O(Σ_{i = 1, 楼层(log n)} (3^{i- 1} - 1))

，但这样的答案不太可能给你满分。

我们可以通过观察我们的总和受相关总和的限制来简化这一点:

    = O(Σ_{i = 1, 楼层(log n)} (3^{i -1}))

。此时(如果不是更早的话)识别其中的幂总和模式将很有用。了解 2⁰ + 2¹ + ... 2^{k - 1} = 2^k 通常很有用> - 1. 这与以 2 为基数的数字表示密切相关，并且可以为任何其他自然数基数编写类似的公式。例如，对于基数 3，它是 2 * 3⁰ + 2 * 3¹ + ... 2 * 3^{k - 1} = 3^k - 1. 这可能足以让您凭直觉得到答案:内循环迭代的总数受上次迭代的内循环迭代次数的常量倍数限制外循环的边界，又以 n 为界。

但是如果您想证明它，那么您可以观察到前一个绑定(bind)表达式中的和本身受相关定积分的限制:

    = O(∫₀^{log n} 3ⁱ d我)

...并且有一个封闭式解决方案:

    = O((3^{log n} - 3⁰)/log 3)

，它本身显然有一个更简单的界限

    = O(3^{log n})

。对数的指数简化为对数参数的线性函数。由于我们只需要一个渐进界限，所以我们不关心细节，因此我们可以直接进入

    = O(n)