复杂度与运行时的实际增长不匹配？

Question

我已经做了一段时间的作业 sheet，我认为无症状复杂性与运行时结果所暗示的存在巨大差异。

下面是程序运行时的table。

|      Input Size     |     Runtime (Seconds)   |
|---------------------|-------------------------|
|       10000         |      0.040533803        |
|---------------------|-------------------------|
|       20000         |      0.154712122        |
|---------------------|-------------------------|
|        30000        |      0.330814060        |    
|---------------------|-------------------------|
|        40000        |      0.603440983        |    
|---------------------|-------------------------|
|        50000        |      0.969272780        |    
|---------------------|-------------------------|
|        60000        |      1.448454467        |

string = "";
newLetter = "a";
for (int i = 500; i < n; i++) {
    string = string + newLetter;
}
return string

除了我的错误之外，为什么算法的复杂性和运行时的增长之间存在差异？

从运行结果来看，程序的时间复杂度似乎是O(n²)。将输入大小加倍似乎会使运行时间增加 4 倍，这表明二次函数？

但是看看程序本身，我 99.9% 确定时间复杂度实际上是 O(n)。

这种差异是否有外来原因？有没有可能运行时结果确实是线性的？

我对这种差异的最佳猜测是 for 循环使下一次迭代变慢（从程序来看是有道理的，因为我认为 Java 编译器必须迭代给定的每个额外的 newLetter）但是那仍然是线性的不是吗？这不是嵌套的 for 循环。

Answer 1

您编写的代码实际上在时间 Θ(n²) 中执行了运行。原因与这部分代码有关：

string = string + newLetter;

在这里，您的意图是说“请在此字符串的末尾附加一个新字符”。然而，Java 实际做的是：

计算表达式 string + newLetter。这使得 brand-new 字符串通过复制 string 的全部内容形成，然后将 newLetter 附加到新字符串的末尾。
将结果赋给string。

这里的问题是，字符串越长，步骤(1)执行的时间就越长，因为所有的字符都必须被复制过来。特别是，如果 string 的长度为 k，则步骤 (1) 需要时间 Θ(k)，因为必须复制 k 个字符。由于 string 的长度与当前循环迭代索引匹配，这意味着完成的工作是

Θ(1 + 2 + 3 + ... + n)

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

= Θ(n²),

这就是为什么你会看到你所看到的情节。

您可以通过使用 StringBuilder 而不是 String 到 assemble 较大的字符串来加快速度。它不会在运行时生成所有中间副本，而是维护一个可以根据需要增长的内部数组。

复杂度与运行时的实际增长不匹配？

Complexity does not match the actual growth of the runtime?

java

time-complexity

runtime

complexity-theory