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