什么数学技术用于比较算法复杂度？

Question

我今天开始阅读《算法导论》，但在做练习时有点困惑。练习1.2.2要求读者：假设我们在同一台机器上比较合并排序和插入排序的实现。对于输入规模为n，插入排序运行8n^2步，而合并排序运行64n log n步。当哪些值的n使用插入排序胜过合并排序？我最初尝试打开Wolfram Alpha并使用其绘制方程图表，但我无法准确地比较两个图表。然后，我尝试选择随机值n（200），用纸笔计算出方程式，然后根据我的结果修改n的值。但这太费时间了。这个练习的正确解决方法是什么？

- Stephen

Answer 1

请参见 这里: 8n² = 64n log₂ n。将两个量放在一个方程式中。

即，大致上当 n = 43 时，插入排序的使用已经达到了极限。

通常情况下，您可以通过解决等式 f(n) = g(n) 来解决以上问题，即解决 f(n) − g(n) = 0，然而，在本例中，分析结果并不美观，因为它将多项式和对数函数混合在一起。我建议尝试几个值，看看结果何时从正变为负。一旦有一个正和一个负点，就可以使用二分法缩小范围。

暴力方式是尝试所有的 n 直到一定程度。由于您已经知道 O(n²) 算法不适用于大型数据集，所以 n 必须相当小。对于我的测试来说，看起来像这样：

PS Home:\> function lb($n){[math]::Log($n)/[math]::Log(2)}  # binary logarithm
PS Home:\> 1..80 | %{,($_,(8*$_*$_),(64*$_*(lb $_)))} | %{"{0}: delta={3}, I={1}, M={2}" -f $_[0],$_[1],$_[2],($_[2]-$_[1])}
...
38: delta=1210,9597126948, I=11552, M=12762,9597126948
39: delta=1024,36393828017, I=12168, M=13192,3639382802
40: delta=824,135922911648, I=12800, M=13624,1359229116
41: delta=610,216460117852, I=13448, M=14058,2164601179
42: delta=382,549232429308, I=14112, M=14494,5492324293
43: delta=141,080604940173, I=14792, M=14933,0806049402
44: delta=−114,240561917371, I=15488, M=15373,7594380826
45: delta=−383,463082570537, I=16200, M=15816,5369174295
46: delta=−666,633601368154, I=16928, M=16261,3663986318
47: delta=−963,796734153668, I=17672, M=16708,2032658463
48: delta=−1274,99519778461, I=18432, M=17157,0048022154
...

（抱歉代码很糟糕，这只是一个非常快速的草图。）

- Joey

---

你为什么假设以2为底的对数？ - Rekin

对数并不重要，因为他展示了这种技术的使用方法（在一个方程中同时使用）。 - Stephen

@Rekin：归并排序将列表分成两个子列表，分别对它们进行排序，然后合并它们。在您看来，哪种对数基数更合适？ - Joey

@Hamish：理由有些错误。是的，谈论复杂度类时给出特定基数是无用的，因为常数因素被忽略了，但在这种情况下，我们正在讨论实际性能数据（步骤的确切数字）。虽然这些遵循复杂度类，但它们仍然具有更多细节，并且为了回答手头的问题，我们实际上需要使用正确的对数 - 在这种情况下是以2为底，但这不是因为数字的二进制表示而是Mergesort工作方式的产物。 - Joey

@Hamish：如果你读了你发的链接，就会很清楚地看到这个算法带来的是以2为底的对数，而没有提到数字的二进制表示。 - Dolphin

Answer 2

有没有某个 n 值使得这两个值相等？

在那个点之上会发生什么？在那个点之下呢？

- user85109

Answer 3

解决方程8n² < 64n lg n，我们得到方程2^(n/8) - n < 0。

有一次我不是在考试，只是做一些练习，我使用了一个工具来查看f(n) = 2^(n/8) - n的图形。

正如在这里提出的问题，没有自然数n使插入排序与归并排序的时间相同，并且对于f(n) < 0，我们得到：

2 <= n <= 43.

希望这能帮助到某些人 :)

- Alan Ricardo

Answer 4

对于n · 43，8n2 · 64n log n和插入排序胜过归并排序 虽然归并排序的最坏情况运行时间为£(n log n)，插入排序的最坏情况运行时间为£(n2)， 但插入排序中的常数因子使其在小n时更快。因此，在子问题变得足够小的时候，在归并排序中使用插入排序是有意义的。 考虑一种修改的归并排序，其中大小为k或更小（对于某个k）的子数组不再分割，而是使用插入排序进行显式排序。

- sahriare

Answer 5

由于这不是代数不等式，因此没有分析方法可以找到n的解决方案。

(1)   8n² < 64n log_2 (n)

所以你需要进行近似处理。有许多数值方法可以实现，因此我们将使用一个快速的Python脚本来完成。

首先，请注意Python的math.log函数是以e为底的对数，因此您需要使用恒等式将原始以2为底的对数转换为以e为底的对数。

(2)   log_2 (n) = log_e (n) / log_e (2)

(Proof.)

使用(1)中的(2)，简化后得到：

(3)   n / log_e (n) <= 8 / log_e (2) 

最终，在脚本中对(3)中的n进行评估。

from math import log as ln

n = 2 # Since f(n) = n/ln (n) is not defined for n < 2.

while (n/ln (n) <= 8/ln (2)):
    n += 1

print (n)

输出 n = 44，这意味着 44 是最小的不满足 (1) 的值。因此，n <= 43 是满足 (1) 的条件，也就是说，在要排序的数组中，元素数量最多为 43 时，插入排序优于归并排序。

- Daniel Muñoz Parsapoormoghadam