我试图比较不同排序算法的时间复杂度(时间执行) . 我正在比较冒泡排序,插入排序,快速排序和融合排序(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]))
1 回答
我认为这里的问题是你的合并(融合)函数的实现方式比它需要的速度慢得多 . 这是你的代码:
您的代码是通过重复获取
L1
的第一个元素,通过线性搜索将其插入L2
然后重复来实现的 . 在最坏的情况下,这种方法的时间复杂度是O(n2),因为第一次插入可能必须扫描n个元素以找到元素的适当位置,第二个可能必须扫描n 1,第三个n 2等这打破了通常使用mergesort获得的美好时间限制 . 通常,实现合并操作以花费时间O(n) . 由于mergesort对数组进行两次递归调用,然后调用merge,因此mergesort的正常时间复杂度遵循这种重复:
其中,使用主定理,求解为O(n log n) . 但是,在您的情况下,由于合并步骤需要时间O(n2),因此运行时为
主定理所说的解决了O(n2) . 换句话说,实现的时间复杂度是二次的,就像冒泡排序和插入排序一样,但由于它对低效算法进行了大量的调用,因此可能具有更高的常数因子 .
要解决此问题,请尝试重写合并算法以在线性时间内运行 . 这可能会使您的代码运行得更快,更快 .