我有一个非常基本的合并和插入排序实现,它涉及一个阈值,低于该阈值,插入排序将用于问题大小为n的子数组,其中合并和插入分类是最基本且广泛可用的:
def hybrid_sort(array: list, threshold: int = 10):
if len(array) > 1:
mid = len(array) // 2
left = array[:mid]
right = array [mid:]
if len(array) > threshold:
hybrid_sort(left)
hybrid_sort(right)
merge(array, left, right)
else:
insertion_sort(array)
除非我完全误解了,否则这意味着我们对这段代码有一个递归关系,广义为:
T(n(=2T(n/2(+O(n^2(
前半部分显示为合并排序,第二部分显示为插入排序操作。
根据主定理,在这种情况下,n提升到log_b(a(将等于n,因为n提升到了log_2(2(,也就是1,所以n^1=n。
那么,我们的F(n(=n^2,它"大于"n,所以根据主定理的情况3,我上面的算法将是F(n(或O(n^2(,因为F(n
考虑到我们知道合并排序是O(nlog(n((,这对我来说似乎不对,我很难理解这一点。我想这是因为我还没有分析过这样一个有条件"如果"检查的算法。
有人能为我阐明这一点吗?
除非阈值本身取决于n,否则插入排序部分根本无关紧要。这与普通合并排序具有相同的复杂性
请记住,接受大小为n的输入的算法的时间复杂性是n的函数,通常很难精确计算,因此我们转而关注该函数的渐近行为。这就是大O符号发挥作用的地方。
在您的情况下,只要threshold是一个常数,这意味着随着n的增长,threshold变得无关紧要,并且所有的插入排序都可以被分组为一个常数因子,从而使整体复杂性成为O((n-threshold) * log(n-threshold) * f(threshold))
,其中f(threshold)
是一个常量。因此将合并排序的复杂性简化为O(n log n)
这里有一个不同的视角,可能有助于了解正在发生的事情。
假设一旦数组大小达到k,就从合并排序切换到插入排序。我们想计算出这种新方法的时间复杂性。为此,我们将设想";差异";在旧算法和新算法之间。具体来说,如果我们不对算法进行任何更改,则合并排序将需要时间Θ(n-logn(才能完成。然而,一旦我们得到大小为k的数组,我们就停止运行mergesort,而是使用插入排序。因此,我们将进行一些观察:
- 存在大小为k的原始阵列的Θ(n/k(个子阵列
- 我们正在跳过对所有这些数组调用mergesort。因此,我们避免为每个θ(n/k(子阵列做θ(k-log-k(功,所以我们避免做θ(n-log-k
- 相反,我们对每个子数组进行插入排序。在最坏的情况下,插入排序在大小为k的数组上运行时需要时间O(k2(。这些数组有θ(n/k(,所以我们添加了O(nk(总功的因子
总的来说,这意味着我们在这个新变体中所做的工作是O(n log n(-O(n log k(+O(nk(。向上或向下拨k将更改已完成的总工作量。如果k是一个固定常数(即k=O(1((,这简化为
O(n log n(-O(n log k(+O(nk(
=O(n log n(-O(n(+O(n(
=O(n log n(
并且渐近运行时与常规插入排序相同。
值得注意的是,随着k变大,最终O(nk(项将主导O(n-log k(项,因此存在一些交叉点,增加k开始减少运行时间。你必须做一些实验来微调何时进行切换。但从经验上讲,将k设置为某个适度的值确实会给你带来很大的性能提升。