1樓：匿名使用者
歸併排序每次會把當前的序列一分為二，然後兩部分各自排好序之後再合併，這樣的話你可以手動模擬出一顆二叉樹來，每一層的總計算量是o(n)的，總的層數是o(logn)的，所以總的複雜度是nlogn
歸併排序的時間複雜度o(n*log n)是怎麼得來的，求大神詳細的講解一下 30
2樓：碧血玉葉花
首先你說歸併排序最壞的情形為o(nlogn)，這是不正確的歸併排序如果不借助輔助空間的話，複雜度為o(n^2)，借助的話就是o(nlogn)(o(nlog2n))歸併排序 平均複雜度是 o(nlogn) 比較快
快速排序快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第乙個元素作為主元。這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。
一種比較常見的優化方法是隨機化演算法，即隨機選取乙個元素作為主元。這種情況下雖然最壞情況仍然是o(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。
所以隨機化快速排序可以對於絕大多數輸入資料達到o(nlogn)的期望時間複雜度。一位前輩做出了乙個精闢的總結：「隨機化快速排序可以滿足乙個人一輩子的人品需求。
」隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到o(n^2)。解決方法是用一種方法進行掃瞄，使沒有交換的情況下主元保留在原位置。
綜合來說快速排序速度最快，時間複雜度最小。希望對你有所幫助！
3樓：汗滌袁希月
搜一下：歸併排序的時間複雜度o(n*log
n)是怎麼得來的，求大神詳細的講解一下
4樓：兔子s歲月
首先，你要理解兩個長度為n/2的的陣列做歸併，這個時間複雜度是o(n)。
然後，因為歸併排序要不斷的把原來陣列分成兩份，這個遞迴的過程是o(logn)。比如說你想要排序的陣列長度為8，然後不斷一的一分為二，就是8——>4——>2——>1。一共拆了3次，2^3 = 8，或者3是以二為底的8的對數。
log就是這樣來的。
然後兩個再相乘，時間複雜度了就是o(nlogn)了。
歸併排序的時間複雜度是多少？
5樓：偉大的小天同學
o(nlogn)和o(nlog2n)是一樣的。。歸併排序如果不借助輔助空間的話，複雜度為o(n^2)，借助的話就是o(nlogn)(o(nlog2n))
6樓：
o(n * 以2為底的n的對數）。
歸併排序c++時間複雜度怎麼算
7樓：聽不清啊
歸併排序的時間複雜度為o(nlog2n)
關於快速排序和歸併排序的時間複雜度
8樓：匿名使用者
首先你說歸併排序最壞的情形為o(nlogn)，這是不正確的歸併排序如果不借助輔助空間的話，複雜度為o(n^2)，借助的話就是o(nlogn)(o(nlog2n))歸併排序 平均複雜度是 o(nlogn) 比較快
快速排序快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第乙個元素作為主元。這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。
一種比較常見的優化方法是隨機化演算法，即隨機選取乙個元素作為主元。這種情況下雖然最壞情況仍然是o(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。
所以隨機化快速排序可以對於絕大多數輸入資料達到o(nlogn)的期望時間複雜度。一位前輩做出了乙個精闢的總結：「隨機化快速排序可以滿足乙個人一輩子的人品需求。
」隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到o(n^2)。解決方法是用一種方法進行掃瞄，使沒有交換的情況下主元保留在原位置。
綜合來說快速排序速度最快，時間複雜度最小。希望對你有所幫助！
〔演算法〕排序的最低時間複雜度為什麼是o（nlogn）
9樓：匿名使用者
這個首先要明確一點，只用到比較的排序演算法最低時間複雜度是o(nlogn)，而
內像桶排這樣的容只需要o(r)(r為桶的大小)
為了證明只用到比較的排序演算法最低時間複雜度是o(nlogn)，首先要引入決策樹。
首先決策樹是一顆二叉樹，每個節點表示元素之間一組可能的排序，它予以京進行的比較相一致，比較的結果是樹的邊。
先來說明一些二叉樹的性質，令t是深度為d的二叉樹，則t最多有2^片樹葉。
具有l片樹葉的二叉樹的深度至少是logl。
所以，對n個元素排序的決策樹必然有n!片樹葉（因為n個數有n!種不同的大小關係），所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較。
而log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=o(nlogn)
所以只用到比較的排序演算法最低時間複雜度是o(nlogn)。
10樓：超級慢
時間複雜度通常括號裡面的是頻度,就是該語句重複的次數一般情況下只需選擇一種基本操作來討論演算法的時間複雜度nlogn就是指執行的次數
具體怎麼個意思也不是太懂 數學學習的不好
連logn都忘記了....
歸併排序分解子問題的時間複雜度為什麼是θ(1)?
11樓：匿名使用者
例如來6 5 4 7 3 8 10 2
會分成6 5 4 7和3 8 10 2
6 5 4 7又分源成6 5 和4 7
3 8 10 2又分成 3 8 和10 2然後對兩個長度的序列進行排序
變成 5 6 4 7 3 8 2 10
根據劃分的結果
對5 6和4 7進行歸併 對3 8和2 10也進行歸併變成 4 5 6 7和2 3 8 10
在對這兩個序列歸併，變成2 3 4 5 6 7 8 10顯然要歸併lgn次
應該是對的
快速排序，希爾排序和堆排序的平均時間複雜度都是O nlog2n ，為什麼說快速排序是最快的
快速排序是用遞迴的思想，用棧來儲存資料，它第n趟最多要確定2 n個數的最終位置。它使用的空間是最多的，用空間換取了時間。例如 快排只是內排序演算法啊，而且在內排序中也並不是最快的，只是快排在大多數情況下效果很好，因為一般的無序元素不會是完全或者近似倒序的。每種排序都有它的優勢。為什麼快速排序比堆排序...
演算法的時間複雜度是指空間複雜度是指
時間複雜度指的是隨著資料規模的增大時間的增率,比如資料量為n,花的時間為n 2,複雜度就是n 2,同理空間複雜度指的是記憶體的開銷。最次的情況就是階乘級別的複雜度,這種演算法是不能用的。演算法的空間複雜度指的是什麼?空間複雜度 space plexity 是對乙個演算法在執行過程中臨時占用儲存空間大...
快速排序方法的時間複雜度為O n 2 n n 1 2中O 是什麼意思
o 1 表示演算法 的執行時間為常量 o n 表示該演算法是線性演算法 o 2n 二分查詢演算法 o n2 對陣列進行排序的各種簡單演算法，例如直接插入排序的演算法。o n3 做兩個n階矩陣的乘法運算 o 2n 求具有n個元素集合的所有子集的演算法o n 求具有n個元素的全排列的演算法o n 表示當...