在《算法导论》中，“tight code”是什么意思？

Question

我正在阅读《算法导论》，作者多次提到“紧凑代码”。这里的“紧凑”是否只是指相对于其他算法，实现同一个算法所需编写的代码更少？

在书中，作者表示插入排序和快速排序都具有“紧凑代码”，这使得算法更快。例如，尽管它们的时间复杂度相同，但一般情况下快速排序比堆排序更快。

当然，“紧凑代码”并不意味着没有适当的格式、额外的空格或空行。

- Yuan Wen

---

好的，这是链接：http://programmers.stackexchange.com/a/210004/216897。 - usamazf

Answer 1

紧密的代码意味着时间复杂度中的常数很小。当你谈论算法并且说它是O(n^2)时，这意味着对于非常大的数字，它会呈二次增长。这可以是1/2*n^2，但也可以是10^7 * n^2或c * n^2。

因此，当这个很小时，它意味着算法或代码是紧密的。显然，在您的算法中，您希望它尽可能地紧密。

- Salvador Dali

---

哦，但是如果“tight”只是指较小的常数，为什么他们不直接说“较小的常数”呢？难道还有其他的含义吗？@萨尔瓦多·达利 - Yuan Wen

@YuanWen 我也认为他们应该明确地告诉这一点。但是，是的，这只意味着更小的常数。这与代码格式或代码编写方式无关。 - Salvador Dali

Answer 2

快速排序和堆排序都具有时间复杂度，用大O表示法表示为O(nlogn)。在实践中，使快速排序比堆排序更快的是被大O分析忽略的常数。Tightcode指的是该常数。

例如，假设有一个循环处理n（一个大输入）次，每次处理需要k个单位时间。因此，总处理时间将是T（处理时间）= k * n（单位时间）。但是，在大O算法分析中，我们只关心算法的增长率（随着输入大小的增加，处理时间增加多少）。因此，这个循环的时间复杂度将是O(n)，其中n代表大的输入大小。这样，我们忽略了不会增长的常数k。 因此，书中大致意思是快速排序的k在实践中比堆排序小。 如果您对为什么快速排序更快感兴趣，请参阅以下链接：快速排序优于堆排序 祝你好运！

- Albert