使用什么数学技术来比较算法的复杂性？

Question

我今天开始阅读"算法简介",但我对其中一个练习感到困惑.

练习1.2.2询问读者

假设我们在同一台机器上比较Merge sort和Insertion Sort的实现.对于大小为n的输入,插入排序以8n ^ 2步进行,而合并排序以64n log n步进行.

n的值是插入排序打败合并排序？

我首先尝试打开W​​olfram Alpha并使用它来绘制方程图,但我无法准确地比较两个图.

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

解决这个问题的正确方法是什么？

Answer 1

见这里:8 n ² = 64 n log ₂ n.把两件事放在一个等式中.

即,大约n = 43是插入排序在这里的有用性限制.

通常你可以通过求解f(n) - g(n)= 0 求解上面的方程式f(n)= g(n)来解决这个问题,然而,这种情况下的分析结果不是很好,因为你正在混合一个具有对数函数的多项式.我只是尝试一些值,看看结果从正面转为负面.一旦你有一个正面和一个负面点,你可以使用二分法来缩小它.

蛮力的方式是简单地尝试所有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
...

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

Answer 2

在两者相等的情况下是否存在n的某些值？

在这一点之上会发生什么？下面？