7.1排序算法的介紹

排序也稱排序算法(SortAlgorithm)，排序是將一組數(shù)據(jù)，依指定的順序進(jìn)行排列的過程。

7.2排序的分類

1.????? 內(nèi)部排序：

指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲器(內(nèi)存)中進(jìn)行排序。

2.????? 外部排序法

數(shù)據(jù)量過大，無法全部加載到內(nèi)存中，需要借助外部存儲(文件等)進(jìn)行排序。

3.????? 常見的排序算法分類

7.3算法的時間復(fù)雜度

度量一個程序(算法)執(zhí)行時間的兩種方法

1.事后統(tǒng)計的方法

這種方法可行，但是有兩個問題:一是要想對設(shè)計的算法的運行性能進(jìn)行評測，需要實際運行該程序;二是所得時間的統(tǒng)計量依賴于計算機(jī)的硬件、軟件等環(huán)境因素，這種方式，要在同一臺計算機(jī)的相同狀態(tài)下運行，才能比較那個算法速度更快。

2.事前估算的方法

通過分析某個算法的時間復(fù)雜度來判斷哪個算法更優(yōu).

7.3.2時間頻度

基本介紹

時間頻度:一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。[舉例說明]

舉例說明-基本案例

比如計算1-100所有數(shù)字之和，我們設(shè)計兩種算法:

舉例說明-忽略常數(shù)項

結(jié)論：

1.???? 2n+20和2n隨著n變大，執(zhí)行曲線無限接近,20可以忽略

2.???? 3n+10和3n隨著n變大，執(zhí)行曲線無限接近,10可以忽略

舉例說明-忽略低次項

假如式子出現(xiàn)了n和n的平方，那么隨著n的變大,n相較于n平方，對式子的整體運算結(jié)果的影響會越來越小，那么就可以忽略

結(jié)論：

(1) 2n^2+3n+10和2n^2隨著n變大,執(zhí)行曲線無限接近，可以忽略3n+10

(2) n^2+5n+20和n^2隨著n變大執(zhí)行曲線無限接近，可以忽略5n+20

結(jié)論:

(1) 隨著n值變大，5n^2+7n和3n^2 +2n，執(zhí)行曲線重合,說明這種情況下,5和3可以忽略。

(2) 而n^3+5n和6n^3+4n ,執(zhí)行曲線分離，說明多少次方是關(guān)鍵

7.3.3時間復(fù)雜度

1. 一般情況下，算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)使得當(dāng)n趨近于無窮大時,T(n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作 T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。

2. T(n)不同，但時間復(fù)雜度可能相同。如:T(n)=n^2+7n+6與T(n)=3n^2+2n+2它們的T(n)不同，但時間復(fù)雜度相同，都為O(n^2)。

3. 計算時間復(fù)雜度的方法:

3.1用常數(shù)1代替運行時間中的所有加法常數(shù)T(n)-n^2+7n+6-→> T(n)n^2+7n+1

3.2修改后的運行次數(shù)函數(shù)中，只保留最高階項T(n)=n^2+7n+1=>T(n)=n^2

3.3去除最高階項的系數(shù)T(n)=n^2 =>? T(n)= n^2 => o(n^2)

7.3.4常見的時間復(fù)雜度

1.???? 常數(shù)階O(1)

2.???? 對數(shù)階O(log2n)

3.???? 線性階O(n)

4.???? 線性對數(shù)階O(nlog2n)

5.???? 平方階O(n^2)

6.???? 立方階O(n^3)

7.???? k次方階O(n^k)

8.???? 指數(shù)階O(2^n)

常見的時間復(fù)雜度對應(yīng)的圖

說明

1.???? 常見的算法時間復(fù)雜度由小到大依次為: O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)，隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低

2.???? 從圖中可見，我們應(yīng)該盡可能避免使用指數(shù)階的算法

?

1.???? 常數(shù)階O(1)

2.???? 對數(shù)階O(log2n)

上面不一定是log2,只不過是因為舉例里面代碼寫的 i = i * 2 具體情況按照實際分析

解釋一下啥時對數(shù)

舉例 2^3 = 8 (2的3次方等于8)

那么就稱3為 以2為底的8的對數(shù)

就相當(dāng)于是，我現(xiàn)在有一個結(jié)果res，再給你一個數(shù)字num，需要求出這個結(jié)果是這個數(shù)字的幾次方

3.???? 線性階O(n)

4.???? 線性對數(shù)階

5.???? 平方階O(n^2)

6.???? 立方階O(n^3)和K次方階O(n^k)

說明:參考上面的O(n^2）去理解就好了，O(n^3)相當(dāng)于三層n循環(huán)，其它的類似

7.3.5平均時間復(fù)雜度和最壞時間復(fù)雜度

1.???? 平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，該算法的運行時間。

2.???? 最壞情況下的時間復(fù)雜度稱最壞時間復(fù)雜度。一般討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。這樣做的原因是:最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的界限，這就保證了算法的運行時間不會比最壞情況更長。

3.???? 平均時間復(fù)雜度和最壞時間復(fù)雜度是否一致，和算法有關(guān)(如圖:)。

備注：Shell 希爾排序

7.4算法的空間復(fù)雜度簡介

7.4.1基本介紹

1.???? 類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。

2.???? 空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時，將占用較多的存儲單元，例如快速排序和歸并排序算法，基數(shù)排序就屬于這種情況

3.???? 在做算法分析時，主要討論的是時間復(fù)雜度。從用戶使用體驗上看，更看重的程序執(zhí)行的速度。一些緩存產(chǎn)品(redis,memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時間.