桶排序時間復(fù)雜度 桶排序時間復(fù)雜度是什么
2020-07-29 天奇生活 【 字體:大 中 小 】
桶排序時間復(fù)雜度:O(N+C),其中C=N*(logN-logM)。桶排序是一個排序算法,工作的原理是將數(shù)組分到有限數(shù)量的桶子里,每個桶子再使用別的排序算法或以遞歸方式繼續(xù)使用桶排序進行排序。
桶排序的平均時間復(fù)雜度為線性的O(N+C),其中C=N*(logN-logM)。如果相對于同樣的N,桶數(shù)量M越大,其效率越高,最好的時間復(fù)雜度達(dá)到O(N)。當(dāng)然桶排序的空間復(fù)雜度為O(N+M),如果輸入數(shù)據(jù)非常龐大,而桶的數(shù)量也非常多,則空間代價無疑是昂貴的。此外,桶排序是穩(wěn)定的。
桶排序的方法
桶排序算法要求,數(shù)據(jù)的長度必須完全一樣,程序過程要產(chǎn)生長度相同的數(shù)據(jù),其方法為:Data=rand()/10000+10000。
每次進行下一次的掃描順序是按照上次掃描的結(jié)果來的,所以設(shè)計上提供相同的兩個桶數(shù)據(jù)結(jié)構(gòu)。前一個保存每一次掃描的結(jié)果供下次調(diào)用,另外一個臨時拷貝前一次掃描的結(jié)果提供給前一個調(diào)用。
在桶排序算法的代碼中,假設(shè)輸入是含n個元素的數(shù)組A,且每個元素滿足0≤ A[i]<1。另外還需要一個輔助數(shù)組B[O..n-1]來存放鏈表實現(xiàn)的桶,并假設(shè)可以用某種機制來維護這些表。
桶排序時間復(fù)雜度 桶排序時間復(fù)雜度是什么
美股開盤時間 美股什么時候開盤
錢塘江大潮的時間 錢塘江大潮時間是什么時候
泉城廣場噴泉時間 濟南泉城廣場噴泉簡介
高鐵檢票時間 高鐵多久開始檢票
五四運動時間 五四運動的起因