什么是二次过程？

Question

我在阅读《Go编程语言》（Donovan和Kernighan所著）这本书，关于他们的例子echo1，他们说："这是一个二次过程，如果参数数量很大，可能会很昂贵，但对于echo来说，这是不太可能的"。什么是二次过程？如果有大量参数，它为什么会很昂贵？

谢谢。

- Omar

---

@KenWhite，我很确定什么是二次方程。但在这个例子中，以及在编程中，什么是二次处理过程？它如何影响性能？如果您有相关链接，我将不胜感激。谢谢！ - Omar

Answer 1

一般来说，二次方会涉及到平方数。在这个上下文中，它意味着过程的成本与输入大小的平方成正比。这是因为使用+=操作符对字符串进行连接在Go中很昂贵，因为字符串是不可变的，并且每次连接都必须在内存中创建一个新的字符串。更有效的字符串连接方法包括将其写入bytes.Buffer并将其转换为字符串或使用strings.Join函数。

- jussius

---

谢谢@jussius。我现在明白了！这正是书中后面讨论的内容。这里的成本是指内存方面吗？ - Omar

然而，如果你将其扩展为连接“H”，“e”，“l”，“l”，“o”，“W”，“o”，“r”，“l”和“d”，并且仍然使用+（或+=）运算符，那么我们现在有一个问题。你从"H" + "e"开始，创建一个长度为2的新数组，在其中复制“H”和“e”。现在你有了"He" + "l"。新数组长度为3，拷贝进去“He”和“l”。重复这个过程直到没有字符串了。每次都会创建一个新数组，因为字符串是不可变的，所以连接操作必须创建一个新的字符串，从而创建一个新的基础数组。这意味着需要大量的分配和复制，特别是对于较早的字符串。 - Kaedys

因此，在大O符号的术语中，for循环是O(N)，并且由于字符串连接需要在每次循环运行时创建一个新字符串（并且由于数组创建也具有O(N)复杂度），因此程序具有O(N^2)复杂度。 - user1301428

@user1301428 嗯，你可以说整个程序只是一个单独的for循环，所以这个循环（即程序）的复杂度为O(n^2)。简单来说，如果你将参数数量加倍，那么就意味着你必须创建两倍的字符串，但也意味着你创建的字符串的平均长度是两倍长（因此成本也是两倍）。因此，总体而言，你需要做四倍的工作。 - jussius

@jussius 一个循环并不一定具有O(n^2)的复杂度，因为它是一个循环:P 它可能只包含O(1)的指令，使得它的复杂度为O(N)。 - user1301428