在“算法入门”中，“紧密代码”是什么意思？

Question

我正在阅读“算法导论”，作者多次提到“严密的代码”。“紧”是否只意味着要编写较少的代码来实现一种算法而不是另一种算法？

在这本书中，作者说插入排序和快速排序都有“严密的代码”，这使得算法更快。例如，快速排序通常比堆排序快，尽管它们的时间复杂度是相同的。

当然，我不认为“紧密代码”意味着没有适当的格式、额外的空格和空白行就可以编写代码。

Answer 1

严格的代码意味着时间复杂度中的常数很小。当你谈到这个算法，并告诉它它是O(n^2)，它意味着，对于一个非常大的数字，它是二次增长。这可以是1/2*n^2，但也可以是10^7 * n^2或c * n^2。

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

Answer 2

快速排序和堆排序都具有时间复杂度，用大O符号O(nlogn)表示。在实践中，快速排序比堆排序快的原因在于它的常数被大O分析忽略了。Tightcode指的是这个常数。

例如，假设有一个处理n(大输入)次数的循环，每次处理都需要k个单位时间。因此，总处理时间为T(处理时间)= k*n (单位时间)。然而，在大O算法分析中，我们只关心算法的增长率(处理时间随着输入大小的增加而增加多少)。因此，这个循环的时间复杂度是O(n)，n代表一个大的输入size.This方法，我们忽略了k，它是一个不会增长的常数。所以这本书的大致意思是，在实践中，quciksort的k比堆小。如果您对快速排序更快的原因感兴趣，那么链接在哪里：Quicksort superiority over Heap Sort祝您好运！