首页 文章

为什么我的mergesort实现比冒泡排序和插入排序慢？

提问于
浏览 次
0

我试图比较不同排序算法的时间复杂度（时间执行） . 我正在比较冒泡排序，插入排序，快速排序和融合排序（mergesort） .

我知道合并排序和快速排序比其他排序更快，但是当我尝试比较这些方法的执行时间时，合并排序总是比其他方法花费更多的时间 . 我尝试了1,000个元素到10,000个元素的列表 . 谁能告诉我为什么？

这是我的mergesort代码：

def inserer(element, ls):
   if  ls==[]:
       return [element]
   elif element<= ls[0]:
       return [element] + ls
   else:
       return [ls[0]] + inserer(element, ls[1:len(ls)])

def fusion(L1,L2):
   if L1==[]:
       return L2
   elif L2==[]:
       return L1
   else:
       return fusion(L1[1:len(L1)],inserer(L1[0], L2))


def triFusion (ls):
   n=len(ls)
   if n==0 or n==1:
       return ls
   else:
       return fusion(triFusion(ls[0:n//2]),triFusion(ls[n//2:n]))
sorting time-complexity mergesort

1 回答

  • 1

    我认为这里的问题是你的合并（融合）函数的实现方式比它需要的速度慢得多 . 这是你的代码：

    def fusion(L1,L2):
   if L1==[]:
       return L2
   elif L2==[]:
       return L1
   else:
       return fusion(L1[1:len(L1)],inserer(L1[0], L2))

    您的代码是通过重复获取 L1 的第一个元素，通过线性搜索将其插入 L2 然后重复来实现的 . 在最坏的情况下，这种方法的时间复杂度是O（n2），因为第一次插入可能必须扫描n个元素以找到元素的适当位置，第二个可能必须扫描n 1，第三个n 2等

    这打破了通常使用mergesort获得的美好时间限制 . 通常，实现合并操作以花费时间O（n） . 由于mergesort对数组进行两次递归调用，然后调用merge，因此mergesort的正常时间复杂度遵循这种重复：

    T（n）= 2T（n / 2）O（n）

    其中，使用主定理，求解为O（n log n） . 但是，在您的情况下，由于合并步骤需要时间O（n2），因此运行时为

    T（n）= 2T（n / 2）O（n2）

    主定理所说的解决了O（n2） . 换句话说，实现的时间复杂度是二次的，就像冒泡排序和插入排序一样，但由于它对低效算法进行了大量的调用，因此可能具有更高的常数因子 .

    要解决此问题，请尝试重写合并算法以在线性时间内运行 . 这可能会使您的代码运行得更快，更快 .

    回复于

相关问题