algorithm - 什么数学技术用于比较算法的复杂性？

Question

我今天开始阅读“算法导论”，但对其中一个练习感到有点困惑。

练习 1.2.2 向读者提问

Suppose we are comparing implementations of Merge sort and Insertion Sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64n log n steps.

For which values of n does insertion sort beat merge sort?

我首先尝试打开 Wolfram Alpha 并用它来绘制方程式的图形，但我无法准确比较这两个图形。

然后我尝试为 n (200) 选择一个随机值，在纸上计算出方程，然后根据我的结果修改 n 的值。
但这花了太长时间。

解决这个练习的正确方法是什么？

Answer 1

参见 here : 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
...

(请原谅可怕的代码；这只是一个非常快速的涂鸦。)