這種排序算法的複雜性是什麼？

template<class T> void sSort(T *A, int first, int last) 
{ 
    if(A[first]>A[last]) 
     swap(A[first],A[last]); 

    if(first+1>=last) 
    return; 
    double k = floor((last-first+1)/3); 


    sSort(A,first,last-k); 
    sSort(A,first+k,last); 
    sSort(A,first,last-k); 
}

我完全理解mergeSort，bubbleSort的複雜性，但我很困惑這一個。這個算法的複雜性是什麼。誰能解釋一下？這種排序算法的複雜性是什麼？

來源

2011-11-10 LuckySlevin

你可以只嘗試不同尺寸的幾個陣列，運行它，看看時間比較數組的大小... – Mehrdad

的計算這是Stooge sort。這是一個算法，用來表明業餘愛好者如果沒有正確分析它們，就不應該實現自己的算法。它的運行時間大約是O（n^3）。

來源

2011-11-11 00:06:21 bdares

謝謝你，這個鏈接幫助我獲得更多的文檔。 – LuckySlevin

誰發明了stoogesort？ – AShelly

這不是太難做了計算。

每次這個算法做3次調用將其自身分裂成3（相等）部分當前步驟的輸入部分。注意：第一個電話和第三個電話是一樣的。
的局部複雜性僅僅是一個O（1）（這意味着恆定），因爲它會做只是交換，一個if並且k

來源

2011-11-10 23:50:57

我對這種事情生疏，但我認爲這是一個有點更多地參與爲三遞歸調用在重疊的值範圍上操作。 – Lars

我實際上堅持3個電話，我不能計算他們，我會有點瘋狂:) – LuckySlevin

實際上算法的作品，但如此緩慢，你可以嘗試運行它:)。算法中不存在任何錯誤。 – LuckySlevin

這種排序算法的複雜性是什麼？

回答

相關問題