Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「排序算法分類與介紹」
介紹
排序是將一組數(shù)據(jù),依指定的順序進(jìn)行排列的過程
排序分類
內(nèi)部排序:指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器中進(jìn)行排序.常見的內(nèi)部排序有:直接插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序、冒泡排序、快速排序、歸并排序、基數(shù)排序。
外部排序:數(shù)據(jù)量過大,無法全部加載到內(nèi)存中,需要借助外部存儲(chǔ)進(jìn)行排序。
算法的時(shí)間復(fù)雜度
度量一個(gè)程序(算法)執(zhí)行時(shí)間的兩種方法:
事后統(tǒng)計(jì)方法這種方法可行,但是有兩個(gè)問題:一是要想對(duì)設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評(píng)測(cè),需要實(shí)際運(yùn)行該程序;二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件\軟件等環(huán)境因素,這種方式,要在同一臺(tái)計(jì)算機(jī)的相同狀態(tài)下運(yùn)行,才能比較哪個(gè)算法速度更快.
事前估計(jì)方法通過分析算法的時(shí)間復(fù)雜度來判斷哪個(gè)算法更優(yōu).
時(shí)間頻度
一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語句執(zhí)行的次數(shù)多,它花費(fèi)時(shí)間就多.一個(gè)算法中語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度.記為T(n).
比如計(jì)算1-100所有數(shù)字之和,有兩種算法
- int total=0;
- int end=100;
- //for循環(huán)計(jì)算
- for(int i=1;i<=end;i++){
- total+=i;
- }
執(zhí)行次數(shù)取決于end長(zhǎng)度.它的T(n)=n+1.
- //直接計(jì)算
- total = (1+end)*end/2;
直接計(jì)算只需執(zhí)行一次即可,它的T(n) = 1.
估算時(shí)間頻度時(shí)注意事項(xiàng):
- 忽略常數(shù)項(xiàng):如T(n)=2n+20和T(n)=2n,隨著n的變大,20可忽略.
- 忽略低次項(xiàng):如T(n)=2n^2+3n+10和T(n)=2n^2,隨著n的變大,3n+10可以忽略.
- 忽略系數(shù):如T(n)=5n^2+7n和T(n)=3n^2+2n,隨著n的變大,5和3可以忽略.
時(shí)間復(fù)雜度
- 一般情況下,算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù),用T(n)表示,若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí),T(n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同量級(jí)函數(shù).記作T(n)=O(f(n)),稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度.
- T(n)不同,但是時(shí)間復(fù)雜度可能相同.如:T(n)=n^2+7n+6與T(n)=3n^2+2n+2,他們的T(n)不同,但是時(shí)間復(fù)雜度都是O(n^2)
- 計(jì)算時(shí)間復(fù)雜度方法
- 用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù).
- 修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng).
- 去除最高階項(xiàng)的系數(shù).
常見的時(shí)間復(fù)雜度
- 常數(shù)階O(1)
無論代碼執(zhí)行了多少行,只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu),那這個(gè)代碼的復(fù)雜度就是O(1)
- int i = 1;
- int j = 2;
- ++i;
- j++;
- int m = i+j;
上述代碼在執(zhí)行的時(shí)候,它消耗的時(shí)間并不是隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng),那么無論這類代碼有多長(zhǎng),即使有幾萬幾十萬行,都可以用O(1)來表示它的時(shí)間復(fù)雜度.
- 對(duì)數(shù)階O(log2n)
- int i = 1;
- while(i<n){
- i = i*2;
- }
在while循環(huán)里面,每次都將i乘以2,乘完之后,i距離n就越來越近了.假設(shè)循環(huán)x次之后,i就大于n了,此時(shí)循環(huán)就結(jié)束了,也就是說2的x次方等于n,那么x= log2n也就是說當(dāng)循環(huán)log2n次以后,這個(gè)代碼就結(jié)束了.因此這個(gè)時(shí)間復(fù)雜度為O(log2n).
- 線性階O(n)
- for(i=1;i<=n;i++){
- j = i;
- j++;
- }
for循環(huán)里面的代碼會(huì)執(zhí)行n遍,因此它消耗的時(shí)間是隨著n的變化而變化的,因此這類代碼都可以使用O(n)來表示它的時(shí)間復(fù)雜度.
- 線性對(duì)數(shù)階O(nlog2n)
- for(int m=1;m<n;m++){
- i = 1;
- while(i<n){
- i = i*2;
- }
- }
這個(gè)線性對(duì)數(shù)階O(log2n)就是將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍.
- 平方階O(n^2)
即雙層for循環(huán),n*m
- 立方階O(n^3)
3層循環(huán)
- K次方階O(n^k)
k次循環(huán)
- 指數(shù)階O(2^n)
常見的算法時(shí)間復(fù)雜度由小到大依次為:O(1)
平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下,該算法的運(yùn)行時(shí)間.
- 最壞情況下的復(fù)雜度稱最壞時(shí)間復(fù)雜度.一般討論的時(shí)間復(fù)雜度是最壞情況下的時(shí)間復(fù)雜度.這樣做的原因是:最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限,這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞情況更長(zhǎng).
- 平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一致,和算法有關(guān)(如下表).
算法的空間復(fù)雜度
- 類似于時(shí)間復(fù)雜度的討論,一個(gè)算法的空間復(fù)雜度(Space complexity)定義為該算法所耗費(fèi)的存儲(chǔ)空間,它也是問題規(guī)模n的函數(shù).
- 空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量.有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān),它隨著n的增大而增大,當(dāng)n較大時(shí),將占用較多的存儲(chǔ)單元,例如快速排序和歸并排序就屬于這種情況.
- 在做算法分析時(shí),主要討論的時(shí)間復(fù)雜度.從用戶體驗(yàn)上看,更看重程序執(zhí)行的速度.一些緩存產(chǎn)品(Redis,Memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時(shí)間.
