1 引言

如題目所示，本節(jié)的精華在于用數(shù)學(xué)解決一個(gè)直覺上看似紛亂復(fù)雜的問題，里面有一些一般性的分析方法，如引入Indicator變量，從而把不確定問題引入到概率框架進(jìn)行分析，一步一步把直覺上混亂的問題理清楚，數(shù)學(xué)之美也就是如此吧！

如果有個(gè)算法在某些情況下表現(xiàn)的很差，在某些情況下又表現(xiàn)的不錯(cuò)，那么你還會(huì)放心的使用該算法嗎？通過下面的分析后你會(huì)很放心使用快速排序算法。

2 Quicksort

2.1 算法描述

2.2 手工演示

• 指針$i$指示的是$\le pivot$的最后一個(gè)，作用是是用來標(biāo)記$\le pivot$和$\ge pivot$的分割狀態(tài)，指針$j$用來遍歷所有元素，每遍歷一個(gè)元素都會(huì)和$pivot$比較，不斷更新$i$的指示狀態(tài)。
  

2.3 實(shí)現(xiàn)

# -*- coding: utf-8 -*-def PARTITION(A, p, r):x = A[r]i = p - 1for j in range(p, r):if A[j] <= x:i = i + 1A[i], A[j] = A[j], A[i]A[i + 1], A[r] = A[r], A[i + 1]return i + 1def QUICK_SORT(A, p, r):if p < r:q = PARTITION(A, p, r)QUICK_SORT(A, p, q - 1)QUICK_SORT(A, q + 1, r)if __name__ == '__main__':A = ['x', 2, 8, 7, 1, 3, 5, 6, 4]print('before sort:', A[1:])QUICK_SORT(A, 1, len(A) - 1)print('after sort:', A[1:])

運(yùn)行結(jié)果：

before sort: [2, 8, 7, 1, 3, 5, 6, 4] after sort: [1, 2, 3, 4, 5, 6, 7, 8]

3 Analysis of quicksort

3.1 worst case

用遞歸樹分析如下：

3.2 best case

應(yīng)用主定理容易得到$T(n)=\Theta (nlogn)$。

3.3 $\frac{1}{10},\frac{9}{10}$case

下面看一種感覺直覺上很差，其實(shí)效果很好的情況。

使用遞歸樹分析：

• 注意$lo{g}_{\frac{10}{9}}n/lo{g}_{2}n=lo{g}_{\frac{10}{9}}2$，這是一個(gè)常數(shù)。

3.4 worst best交替情況

• 好壞交替的情況下，最后仍然是好的！

3.5 random case

上面從矛盾的特殊性上讓直覺有一個(gè)直觀的感受，只要不是特別極端（如一個(gè)初始狀態(tài)是逆序的數(shù)列），貌似大部分情況下都是ok的，下面用概率框架確認(rèn)這種直觀的感覺是正確的。

• 對(duì)于離散不確定問題，要引入概率框架進(jìn)行討論，首先要引入一個(gè)合適的隨機(jī)變量，這里引入指示器（Indicator）隨機(jī)變量，這個(gè)變量在機(jī)器學(xué)習(xí)算法中使用更為廣泛，看似簡(jiǎn)單的一個(gè)定義，卻可以化繁為簡(jiǎn)的用一個(gè)表達(dá)式表示所有情況。
  

• 至此，已經(jīng)進(jìn)入到概率框架，可以暫時(shí)忘記之前的算法問題背景：
  

• 概率世界都是是不確定的，研究概率大目的是找出不確定問題的平均特性，如期望、方差等，這里只關(guān)注期望。

• 下面的推到中用到了期望的線性可加性和獨(dú)立可乘性。

分割的獨(dú)立性：第一次分割后，數(shù)組分為第a部分和第b部分，a部分具體在哪個(gè)位置分割已經(jīng)和第一次分割沒有關(guān)系。

• 猜想$E[T(n)]\le anlgn$，a足夠大，接下來數(shù)學(xué)歸納法要登場(chǎng)了！，首先有一個(gè)數(shù)學(xué)事實(shí)要知道，這個(gè)結(jié)論也是用數(shù)學(xué)歸納法容易證明：
  

• 使用數(shù)學(xué)歸納法證明$E[T(n)]\le anlgn$
  

4 總結(jié)

• 從上面的分析中可以看到，快速排序大概率是$\Theta (nlogn)$的，在實(shí)際應(yīng)用中快速排序往往是歸并排序速度的2倍以上，如果在細(xì)節(jié)上對(duì)算法微調(diào)，則可以表現(xiàn)出更好的性能.

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的六、Analysis of quicksort的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。