1

考虑以下一段 C++ 代码：

string s = "a";
for (int i = 0; i < n; i++) {
    s = s + s; // Concatenate s with itself.
}

通常，在分析一段代码的时间复杂度时，我们会确定内循环做了多少工作，然后将其乘以外循环运行的次数。但是，在这种情况下，内部循环完成的工作量因迭代而异，因为正在构建的字符串越来越长。

您将如何分析此代码以获得大 O 时间复杂度？

4

1 回答 1

4

该函数的时间复杂度为 Θ(2 n )。要了解这是为什么，让我们看看这个函数做了什么，然后看看如何分析它。

对于初学者，让我们跟踪 n = 3 的循环。在迭代 0 之前，字符串s是 string "a"。s迭代 0使 to的长度加倍s = "aa"。s迭代 1使 to的长度加倍s = "aaaa"。然后迭代 2 将 的长度s加倍s = "aaaaaaaa"。

如果您注意到，在k循环迭代之后，字符串的长度s为 2 k。这意味着循环的每次迭代将花费越来越长的时间来完成，因为将字符串s与自身连接起来需要越来越多的工作。具体来说，k循环的第 th 次迭代将花费时间 Θ(2 k ) 来完成，因为循环迭代构造了一个大小为 2 k+1的字符串。

我们可以分析此函数的一种方法是将内部循环的最坏情况时间复杂度乘以循环迭代次数。由于每次循环迭代需要时间 O(2 n ) 来完成并且有 n 次循环迭代，我们会得到这段代码需要时间 O(n · 2 n ) 来完成。

然而事实证明，这种分析并不是很好，实际上会高估这段代码的时间复杂度。确实，这段代码运行时间为 O(n · 2 n )，但请记住，大 O 表示法给出了一段代码运行时间的上限。这意味着此代码运行时的增长率不大于 n · 2 n的增长率，但这并不意味着这是一个精确的界限。事实上，如果我们更精确地查看代码，我们可以得到更好的界限。

让我们首先尝试对已完成的工作做一些更好的说明。这个循环中的工作可以分成两个更小的部分：

  • 在循环头部完成的工作，它递增i并测试循环是否完成。
  • 在循环体中完成的工作，它将字符串与自身连接起来。

在这里，当考虑这两个点的工作时，我们将考虑所有迭代中完成的工作总量，而不仅仅是一次迭代。

让我们看一下其中的第一个 - 循环头完成的工作。这将运行 n 次。每次，这部分代码只会做 O(1) 的工作增量i，测试它n，并决定是否继续循环。因此，这里完成的总工作是 Θ(n)。

现在让我们看看循环体。正如我们之前看到的，迭代 k 在迭代 k 上创建了一个长度为 2 k+1的字符串，这大约需要 2 k+1的时间。如果我们在所有迭代中总结这一点，我们得到完成的工作是（粗略地说）

2 1 + 2 2 + 2 3 + ... + 2 n+1。

那么这个金额是多少呢？以前，我们通过注意到

2 1 + 2 2 + 2 3 + ... + 2 n+1。

< 2 n+1 + 2 n+1 + 2 n+1 + ... + 2 n+1

= n · 2 n+1 = 2(n · 2 n ) = Θ(n · 2 n )

然而，这是一个非常弱的上限。如果我们更加细心，我们可以将原始总和识别为几何级数的总和，其中 a = 2 和 r = 2。鉴于此，这些项的总和可以精确计算为

2 n+2 - 2 = 4(2 n ) - 2 = Θ(2 n )

换句话说，循环体在所有迭代中所做的总工作是 Θ(2 n )。

循环完成的总工作由循环维护中完成的工作加上循环体中完成的工作给出。这适用于 Θ(2 n ) + Θ(n) = Θ(2 n )。因此，循环完成的总功为 Θ(2 n )。这增长得非常快，但远没有 O(n · 2 n ) 快，这是我们最初的分析给我们的。

简而言之，在分析循环时，您始终可以通过将循环的迭代次数乘以该循环的任何一次迭代上所做的最大工作来获得一个保守的上限。但是，进行更精确的分析通常可以为您提供更好的界限。

希望这可以帮助！

于 2013-04-29T20:10:17.877 回答