爲什麼我的mergesort實現比冒泡排序和插入排序慢？

Question

我試圖比較不同排序算法的時間（時間執行）的複雜性。我比較冒泡排序，插入排序，快速排序和融合排序（mergesort）。

我知道合併排序和快速排序比其他排序快，但是當我嘗試比較這些方法的執行時間時，合併排序總是比其他排序花費更多的時間。我嘗試了1000個元素到10,000個元素的列表。誰能告訴我爲什麼？

這裏是我的歸併代碼：

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])) 

Answer 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（n ），因爲第一次插入可能必須掃描n個元素以找到元素的正確位置，第二次插入可能必須掃描n + 1，第三個n + 2等等。

這打破了通常用mergesort獲得的美好時間界限。通常，執行合併操作需要花費時間O（n）。由於歸併排序使得在陣列上半兩個遞歸調用一樣大原，然後呼叫合併，歸併的正常時間複雜度服從該復發：

T（N）= 2T（N/2）+ O（N ）

其中使用主定理解決O（n log n）。然而，在你的情況下，由於您的合併步驟花費的時間爲O（n ），運行時是

T（N）= 2T（N/2）+ O（N ）

大師定理所說的解決O（n ）。換句話說，實現的時間複雜度是二次的，就像冒泡排序和插入排序一樣，但由於它會對低效算法進行大量的調用，因此可能具有更高的常數因子。

要解決此問題，請嘗試重寫您的合併算法以線性時間運行。這可能會讓你的代碼運行得更快，速度更快。