1樓：Yan
假如每次都平分, 那麼就有 (n + 2 *(n/2) + 4 *(n/4) .... + kn/k), 這就是總的執行次數. 就等於
k* n 次.
不管怎麼平分, 一共執行 k 次, 所以就有 n * (1/2)^k = 1, 則有2^k = n, k = log2n(以二為底, n 的對數), 因為每次都需要執行大約 n 次移動, 所以有O(nlogn).
不知道對不對, 是根據二分法的思想算出來的, 不考慮特殊情況, 大約平分了這麼多次.
2樓：
摘自《資料結構與演算法分析——C語言描述》，個人認為講得還是相當通俗易懂的，而且平均、最好、最壞這三個時間複雜度都有。
基本的快速排序關係：
平均時間複雜度：
2. 最好時間複雜度：
3. 最壞時間複雜度：
3樓：
其實這個可以求精確解的吧.
直接設對規模 的陣列排序需要的時間期望為 , 期望其實就是平均複雜度換個說法.
隨手寫個快排:
qs[{}]
={};qs
:=Join[qs
@Select[,#
<=x&
],,qs
@Select[,#
>x&]];空表的時候不用排, 所以初值條件就是 .
所謂快排就是隨便取出乙個數,一般是第乙個數,然後小於等於他的放左邊, 大於他的的排右邊.
比如左邊 個那接下來還要排: 的時間.
然後 多少那是不確定的, 遍歷 , 出現概率都是相等的.
另外分割操作本身也要時間 , 操作花費是線性時間 , 這也要加進去, 所以一共是:
注意和式展開就是 到 加了兩遍
然後就是喜聞樂見的解遞推了:
這個一階非線性齊次差分方程的解是:
嗯, 所以確切的說快排演算法的小常數是兩倍的分割速度.
讓函式在無窮遠處展開
最高端是 所以就是 了.
4樓：
陣列有n個元素，因為要遞迴運算，算出支點pivot的位置，然後遞迴呼叫左半部分和有半部分，這個時候理解上是若第一層的話就是n/2，n/2，若是第二層就是n/4,n/4,n/4,n/4這四部分，即n個元素理解上是一共有幾層2^x=n，x=logn，然後每層都是n的複雜度，那麼平均就是O(nlogn)的時間複雜度。但這種肯定是平均情況，如果你是標準排序的情況下，如果已經是ascending的順序，那麼遞迴只存在右半部分了，左半部分都被淘汰了。(n-1)*(n-2)*....
*1，這個複雜度肯定就是O(n^2)，這種情況還不如用插入排序。
5樓：
對資料Data = ：
T（n）是QuickSort（n）消耗的時間；
P（n）是Partition(n)消耗的時間；
（注：Partition專指把n個資料分為大小2份的時間）注：ln( n ) > 1/2 + 1/3 ... + 1/n證明：
6樓：王一文
快速排序演算法的時間複雜度分析[詳解Master method]
這位博主回答的很好。而且快排的worse case 是 O(n^2)
7樓：於天航
對於乙個iOS開發者，我的證明方法是這樣：
Google搜尋「快速排序的時間複雜度」之後大家都說是O(nlogn)，於是我就記下來了。
所以取決於你的需求，不拿來考試的話用高等數學公式推導演算法時間複雜度時間很蛋疼的事情。。。
8樓：Runtian Zhou
假設排序後陣列為
首先設定indicator random variable ，表示第i位和第j位被比較的事件，由快排特性可知，第i位和第j位比較當且僅當在中選取或作為比較的pivot時才會發生，不然就會被分到pivot兩邊，就不可能比較了，所以
由期望的線性特性可知，總的比較的次數的期望為任意兩個陣列元素比較的期望之和，所以
,之後把資料帶進去就行了，每一層都是個調和級數，總共有n層，所以最後比較次數的期望就在中，大致就是這個思路
具體證明可以參考我們的課件：https://drive.google.com/file/d/0B4z2gzEmkDDCa0tNQWMtNTk1Z2s/view
9樓：
非嚴格證明，每次把n劃分為n/10和9n/10，算是不太好的劃分了，則T(n)=T(n/10)+T(9n/10)+cn，用樹結構展開，把每層代價加起來就是了。
嚴格證明會用到主定理和概率論知識，看《演算法導論》
10樓：
證明過程挺複雜的。演算法導論上有，用主定理證明的，很詳細。但是沒法簡化，要寫在這裡可真不容易。
參見：http://
my.oschina.net/zhudibrian/blog/167722
如何計算程式的時間複雜度中的常數？
XonAzis 所謂的 常數 其實是對於時間複雜度而言的。眾所周知，要計算乙個演算法的時間複雜度，都會想想將某變數設定為無窮大，那麼最後會得出乙個什麼式子。就拿乙個函式來做乙個簡單的例子好了。那麼如果我們把x設為無窮大，那麼我們可以看到，那個 會變得異常之大，以至於剩下的 都可以省略，那麼最後計算出...
如何理解演算法時間複雜度分析時的常數
jsx 例如你要求解一列數的和，需要輸入 求解 輸出。我們一般認為這是O n 的。但是我們基本上要輸入數列的長度 數列的內容 求和 輸出結果，這至少要2n 2步，這兩個2都是常數。但我們仍認為這是O n 的。你可以看一下大O表示法的定義，基本上是用乙個函式f x 分別乘乙個數，在x足夠大的時候 壓住...
如何以O N 的時間複雜度找到N N矩陣的乙個區域性最小值？
假設你這個矩陣是個凸凹不平的面，那麼極值就是面和另外乙個平行平面相切的地方，梯度下降法就可以，二階偏導數為零即是極值點，但區域性最小值沒什麼意義，區域性到底多大，哪個區域性你又沒給出。修改一下，O N 時間只夠掃瞄常數條線，所以既然你說了，那肯定是打靶法，先打 2個離散點，再判斷周圍九宮格，過濾重複...