时间戳

首页 > 解决方案 > 以下依赖循环的时间复杂度是多少？

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

问题描述

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

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

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

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

非常感谢！

PS：我知道这j *= 2不会影响for循环。

标签： calgorithmdata-structurestime-complexity

解决方案

正如您所认识到的，计算循环嵌套的复杂性，其中内部循环的边界因外部循环的不同迭代而变化，并不像两个迭代计数的简单相乘那样容易。您需要更深入地查看以获得最紧密的界限。

这个问题可以看作是询问内循环的主体执行了多少次，作为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, floor(log n ) (3 i -1 - 1))

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

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

    = O(Σ i = 1, floor(log n ) (3 i -1 ))

. 在这一点上（如果不是更早的话），识别其中的功率总和模式将是有用的。知道 2 0 + 2 1 + ... 2 k - 1 = 2 k - 1 通常很有用。这与以 2 为基数的数字表示密切相关，并且可以为任何其他自然数基数编写类似的公式. 例如，对于基数 3，它是 2 * 3 0 + 2 * 3 1 + ... 2 * 3 k - 1 = 3 k - 1。这可能足以让您凭直觉得出答案：内循环迭代受外循环最后一次迭代的内循环迭代次数的恒定倍数限制，而外循环又以n为边界。

但是如果你想证明它，那么你可以观察到上一个有界表达式中的和本身是由一个相关的定积分限制的：

    = O(∫ 0 log n 3 i d i )

...并且有一个封闭形式的解决方案：

    = O((3 log n - 3 0 ) / log 3)

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

    = O(3 log n )

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

    = O(n)

推荐阅读