1.排序算法介紹
排序也稱排序算法?(Sort Algorithm)搔驼，排序是將一?組數(shù)據(jù)，依指定的順序進(jìn)行排列?的過程蚜印。
-
排序的分類：
- 內(nèi)部排序:
指將需要處理的所有數(shù)據(jù)都加載?到內(nèi)部存儲(chǔ)器中進(jìn)行排序寨蹋。
- 內(nèi)部排序:
- 外部排序法：
數(shù)據(jù)量過大，無(wú)法全部加載到內(nèi)?存中岳遥，需要借助外部存儲(chǔ)進(jìn)行
排序。
- 外部排序法：
- 常見的排序算法分類(見右圖):
2.算法的時(shí)間復(fù)雜度
2.1度量一個(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è)算法速度更快。
事前估算的方法?通過分析某個(gè)算法的時(shí)間復(fù)雜度來(lái)判斷哪個(gè)算法更優(yōu).
2.2時(shí)間頻度
- 時(shí)間頻度：一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例试和，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多讯泣，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度阅悍。記為T(n)好渠。
- 忽略常數(shù)項(xiàng)
- 忽略低次項(xiàng)
- 忽略系數(shù)
2.3時(shí)間復(fù)雜度
一般情況下，算法中的基本操作語(yǔ)句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)节视，用T(n)表示拳锚，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無(wú)窮大時(shí)寻行，T(n) / f(n) 的極限值為不等于零的常數(shù)霍掺，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作 T(n)=Ｏ( f(n) )拌蜘，稱Ｏ( f(n) ) 為算法的漸進(jìn)時(shí)間復(fù)雜度杆烁，簡(jiǎn)稱時(shí)間復(fù)雜度。
T(n) 不同简卧，但時(shí)間復(fù)雜度可能相同兔魂。 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的T(n) 不同，但時(shí)間復(fù)雜度相同举娩，都為O(n2)析校。
-
計(jì)算時(shí)間復(fù)雜度的方法：
用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù) T(n)=n2+7n+6 => T(n)=n2+7n+1
修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng) T(n)=n2+7n+1 => T(n) = n2
去除最高階項(xiàng)的系數(shù) T(n) = n2 => T(n) = n2 => O(n2)
2.4常見的時(shí)間復(fù)雜度
-
常數(shù)階O(1)
無(wú)論代碼執(zhí)行了多少行铜涉，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)智玻，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)
上述代碼在執(zhí)行的時(shí)候，它消耗的時(shí)候并不隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng)骄噪，那么無(wú)論這類代碼有多長(zhǎng)尚困，即使有幾萬(wàn)幾十萬(wàn)行，都可以用O(1)來(lái)表示它的時(shí)間復(fù)雜度链蕊。
- 對(duì)數(shù)階O(log*****2******n*)
說(shuō)明：在while循環(huán)里面事甜，每次都將 i 乘以 2，乘完之后滔韵，i 距離 n 就越來(lái)越近了逻谦。假設(shè)循環(huán)x次之后，i 就大于 2 了陪蜻，此時(shí)這個(gè)循環(huán)就退出了邦马，也就是說(shuō) 2 的 x 次方等于 n，那么 x = log2n也就是說(shuō)當(dāng)循環(huán) log2n 次以后，這個(gè)代碼就結(jié)束了滋将。因此這個(gè)代碼的時(shí)間復(fù)雜度為：O(log2n) 邻悬。 O(log2n) 的這個(gè)2 時(shí)間上是根據(jù)代碼變化的，i = i * 3 随闽，則是 O(log3n) .
- 線性階O(n)
說(shuō)明：這段代碼父丰，for循環(huán)里面的代碼會(huì)執(zhí)行n遍，因此它消耗的時(shí)間是隨著n的變化而變化的掘宪，因此這類代碼都可以用O(n)來(lái)表示它的時(shí)間復(fù)雜度
- 線性對(duì)數(shù)階O(nlog*****2******n*)
說(shuō)明：線性對(duì)數(shù)階O(nlogN) 其實(shí)非常容易理解蛾扇，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是n *O(logN)魏滚，也就是了O(nlogN)
-
平方階O(n^2)
?1559733454884.png
說(shuō)明：平方階O(n2) 就更容易理解了镀首，如果把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是
O(n2)鼠次，這段代碼其實(shí)就是嵌套了2層n循環(huán)更哄，它的時(shí)間復(fù)雜度就是O(nn)，即O(n2) 如果將其中一層循環(huán)的n改成m须眷，那它的時(shí)間復(fù)雜度就變成了O(mn)
立方階O(n^3)
k次方階O(n^k)
指數(shù)階O(2^n)
常見的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) 竖瘾，隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大花颗，算法的執(zhí)行效率越低
從圖中可見捕传，我們應(yīng)該盡可能避免使用指數(shù)階的算法
2.5平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，該算法的運(yùn)行時(shí)間扩劝。
- 最壞情況下的時(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)(如圖:)簇秒。
3.算法的空間復(fù)雜度簡(jiǎn)介
- 類似于時(shí)間復(fù)雜度的討論鱼喉，一個(gè)算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問題規(guī)模n的函數(shù)趋观。
- 空間復(fù)雜度(Space Complexity)是對(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í)間.
