1樓：cfv呆呆獸
根據t(n) = t(ðn) + o(n) (0 < ð <1) 則有 t(n) = o(n)
因此關鍵問題
是怎樣解決劃分標準的問題, 因此產生下列線性時間找中位數的演算法:
將陣列a有n個元素, 劃分成5個一組, 則共有[n/5]個元素, 對於每組用一般的排序找中位數,需要25次, 則總共需要o(25*[n/5]) = o(n), 然後在這些中位數中遞迴找其中位數需要t(n/5)次,然後以找到的中位數x來作為劃分標準則顯然劃分時間為o(n), 再遞迴的劃分, 顯然最多有3n/4的元素小於或大於x, 則選擇中位數的總複雜度為:
t(n) = o(n) + t(n/5) + t(3n/4) 有t(n) = o(n)。
因此快速排序的複雜度為t(n) = 2t(n/2) + o(n) 有:t(n) = nlogn。
但最壞情況下複雜度為o(n^2)，出現此條件的情況是n個數原來就已經按照規定要求排好序了。
對於輸入為n個數進行快速排序演算法的平均時間複雜度是 o（nlog2n） 請講的通俗易懂些 捷徑
2樓：百度使用者
這不是平均吧，是最優吧。
先要知道大寫o和小寫o，極限什麼的。
快速排序法的平均時間複雜度是多少？
3樓：匿名使用者
平均時間複雜度是o(nlog2n).
4樓：匿名使用者
平均時間複雜度o（nlogn），最壞時間複雜度o（n*n）,輔助空間o（logn）
5樓：
nlog2n
n倍以2為底n的對數。
快速排序演算法的平均時間複雜度
6樓：匿名使用者
nlogn的底數預設是2
因為資訊學裡很多演算法都是以二分為思想的！！！這個很重要！！！二分能降低時間複雜度，將o(n)降到o(logn)，將o(n^2)降到o(nlogn)
像快速排序，二分查詢，二分答案，線段樹這些都用到了二分思想！！！
7樓：
nlogn就是nlog2n。。在資訊學中，log預設是以2為底的。
快速排序演算法在平均情況下的時間複雜度為 求詳解
8樓：匿名使用者
時間複雜度為o(nlogn) n為元素個數
1. 快速排序的三個步驟：
1.1. 找到序列中用於劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分
所以對於n個元素其排序時間為
t(n) = 2*t(n/2) + n （表示將長度為n的序列劃分為兩個子序列，每個子序列需要t(n/2)
的時間，而劃分序列需要n的時間）
而 t(1) = 1 （表示長度為1的序列無法劃分子序列，只需要1的時間即可）
t(n) = 2^logn + logn * n （n被不斷二分最終只能二分logn次（最優的情況,每次選取
的元素都均分序列））
= n + nlogn
因此t(n) = o(nlogn)
以上是最優情況的推導，因此快速排序在最優情況下其排序時間為o(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為氣泡排序，t(n) = t(n - 1) + n (每次選取的元素只能將序列劃分為
一段，即自身是 最小元素或最大元素)
因此t(n) = n * (n-1) / 2 相當於o(n^2)
9樓：匿名使用者
時間複雜度為o（nlogn）n是多少元素
1。快速排序的三個步驟：
1.1。查詢序列用於劃分的序列中的元素
1.2元素劃分的序列
1.3 1,2兩個步驟的過程不斷重複，兩個序列劃分指導序列不能被細分
n個元素的排序條件為t（n）= 2 * t（n / 2個）+ n（表示序列分為兩個子序列中的n的長度，每個子序列需要到t（n / 2個）
時間除以
t（1）= 1（序列的長度不能被劃分為子序列，序列的n個）只需要1罐）
t（n）= 2 ^ logn + logn * n（n為不斷二分法最後只有兩點：logn（最佳，各選擇
平均序列的元素））
= n + nlogn
因此，t（n）= o（nlogn ）
以上是派生的理想情況下，快速排序排序在最佳的情況下，時間為o（nlogn）通常平均
我們也相信，這個值。
在最壞的情況下，它會淪為氣泡排序，t（n）= t（n - 1個）+ n（每次選擇元素序列分為
一些，這是他們自己的元素是最小的或最大的元素）
t（n）= n *（n-1）/ 2，相當於為o（n ^ 2）
10樓：雨的恩惠
正如歸併排序一樣，快速排序也是遞迴的，因此，他的分析需要求解一個遞推公式。我們將對快速排序進行這種分析，假設有一個隨機的樞紐元（不用三數中值分割法），對一些小的檔案也不使用截止範圍。和歸併排序一樣，取t(0)=t(1)=1,快速排序的執行時間等於兩個遞迴呼叫的執行時間加上花費在分割上的限行時間（樞紐元的選取僅花費常數時間）。
我們得到基本的快速排序關係：
t(n)=t(i)+t(n-i-1)+**
其中，i=|s1|是s1中的時間個數。我們還將考查三種情況。
最壞情況的分析：
樞紐元始終是最小元素。此時i=0，如果我們忽略無關緊要的 t(0)-1,那麼遞推關係為
t(n0=t(1)+c(sum+=i;i in (2,n])= o(n^2)
最好情況：
在最好的情況下，樞紐元正好位於中間，t(n)=o(n* log(n))
平均情況的分析：
t(n)=o(n*logn)
《資料結構與演算法分許（c語言描述）》 片段，字太多了，全是公式推導，打了一部分
11樓：郝霞佛念
快速排序時間複雜度下界為o(nlogn)，最壞情況為o(n^2)
快速排序的平均時間複雜度為o(nlogn)。
快速排序的時間複雜度
12樓：匿名使用者
1.快速排序-時空複雜度：
快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為o(nlogn)，最壞情況為o(n^2)。在實際應用中，快速排序的平均時間複雜度為o(nlogn)。
快速排序在對序列的操作過程中只需花費常數級的空間。空間複雜度s(1)。
但需要注意遞迴棧上需要花費最少logn最多n的空間。
2.快速排序-隨機化演算法：
快速排序的實現需要消耗遞迴棧的空間，而大多數情況下都會通過使用系統遞迴棧來完成遞迴求解。在元素數量較大時，對系統棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設定一個閾值，在每次遞迴求解中，如果元素總數不足這個閾值，則放棄快速排序，呼叫一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統遞迴棧的頻繁存取，節省了時間的消費。
一般的經驗表明，閾值取一個較小的值，排序演算法採用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值t=10，排序演算法用選擇排序。
閾值不要太大，否則省下的存取系統棧的時間，將會被簡單排序演算法較多的時間花費所抵消。
另一個可以參考的方法，是自行建棧模擬遞迴過程。但實際經驗表明，收效明顯不如設定閾值。
3.快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。
這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是o(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。
實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入資料達到o(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：
「隨機化快速排序可以滿足一個人一輩子的人品需求。」
隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到o(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。
4.設要排序的陣列是a[0]……a[n-1]，首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設定兩個變數i、j，排序開始的時候：i=0，j=n-1；
2）以第一個陣列元素作為關鍵資料，賦值給key，即 key=a[0]；
3）從j開始向前搜尋，即由後開始向前搜尋（j=j-1），找到第一個小於key的值a[j]，並與a[i]交換；
4）從i開始向後搜尋，即由前開始向後搜尋（i=i+1），找到第一個大於key的a[i]，與a[j]交換；
5）重複第3、4、5步，直到 i=j； (3,4步是在程式中沒找到時候j=j-1，i=i+1。找到並交換的時候i， j指標位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另迴圈結束)
例如：待排序的陣列a的值分別是：（初始關鍵資料：x=49） 注意關鍵x永遠不變，永遠是和x進行比較，無論在什麼位子，最後的目的就是把x放在中間，小的放前面大的放後面。
a[0] 、 a[1]、 a[2]、 a[3]、 a[4]、 a[5]、 a[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找》x的值，65>49,兩者交換，此時：i=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於x的值，97>49,兩者交換，此時：i=4,j=6 )
此時再執行第三步的時候就發現i=j，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞迴呼叫此過程——在以49為中點分割這個資料序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列，根據這種思想對於上述陣列a的快速排序的全過程如圖6所示：
初始狀態
進行一次快速排序之後劃分為 49
分別對前後兩部分進行快速排序 經第三步和第四步交換後變成 完成排序。
經第三步和第四步交換後變成 完成排序。
使用者輸入正整數n，若n為奇數，程式計算出數列
c語言main print d i sum i else print d i sum i print d sum s 0 if n mod 2 0 output s 這個要看你是用什麼來實現了，是vb還是c還是c 編寫程式。輸入任意整數n，計算1到n的奇數和。解題思路 迴圈判斷 bai1到n的每一個...
c語言題目輸入n個數到一維陣列a中求均方差
c語言中陣列定義的時候必須制定資料的個數，如 1 int a 10 2 define n 10 int a n n 為常量 int n 10 int a n 這種定義陣列的方式是錯誤的，因為n是變數 直接用陣列名字呼叫即可。如 int a 10 0,1,2,3,4,5,6,7,8,9 定義一個陣列變...
c語言輸入n判斷n是不是完數，C語言輸入n，判斷n是不是完數
include int main void if sum n puts yes else puts no return 0 include int isdata int data int isdata int ndata if n 6 return 0 int temp,sum x表示要判斷的數，t...