算法
算法定義
算法（Algorithm）： 是解決 特定問(wèn)題 求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。
算法特性
算法有五個(gè)基本特性： 有限性、確定性、輸入、輸出和可行性。
輸入輸出： 算法具有至少一個(gè)或多個(gè)輸出，具有零個(gè)或多個(gè)輸入。
有限性： 算法在執(zhí)行有限步驟后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)，并且每一個(gè)步驟都在可接受的時(shí)間內(nèi)完成。
確定性： 算法的每一步驟都具有正確的定義，不會(huì)出現(xiàn)二義性。
可行性： 算法的所有操作都必須是可行的，每一步驟都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。
算法設(shè)計(jì)要求（評(píng)價(jià)優(yōu)劣的基本標(biāo)準(zhǔn)）
（1） 正確性： 在合理的數(shù)據(jù)輸入下，能夠在有限的運(yùn)行時(shí)間內(nèi)通過(guò)優(yōu)先步驟得到正確的結(jié)果。
（2） 可讀性： 算法設(shè)計(jì)的另一個(gè)目的是為了便于閱讀、理解和交流
（3） 健壯性： 當(dāng)輸入不合法時(shí)，算法能對(duì)其做出相關(guān)處理，而不是產(chǎn)生異?；蚰涿畹慕Y(jié)果
（4） 高效性： 高效性包括時(shí)間和空間兩方面，設(shè)計(jì)算法一個(gè)盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求
算法效率的度量方法
衡量算法效率的方法 主要有兩類： 事后統(tǒng)計(jì)法 和 事前分析估計(jì)法 。
事后統(tǒng)計(jì)法
事后統(tǒng)計(jì)法： 這種方法主要是通過(guò)設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低。
這個(gè)方法是有很大的 缺陷 的：
- 必須算法事先編制好程序，需要花費(fèi)大量時(shí)間和精力，還不能確定是不是糟糕的算法；
- 時(shí)間的比較很依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素，有時(shí)會(huì)掩蓋算法本身的優(yōu)劣；
- 算法的測(cè)試數(shù)據(jù)設(shè)計(jì)困難，并且程序的運(yùn)行時(shí)間通常與測(cè)試數(shù)據(jù)的規(guī)模有很大關(guān)系，效率高的算法在小的測(cè)試數(shù)據(jù)面前往往得不到體現(xiàn)，比如10個(gè)數(shù)的排列，無(wú)論用什么算法，差異幾乎為零。
事前分析估計(jì)法
事前分析估計(jì)： 在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。
不考慮計(jì)算機(jī)的軟硬件等環(huán)境因素，影響算法時(shí)間的因素有問(wèn)題規(guī)模和算法好壞，其中最主要因素是問(wèn)題規(guī)模。
問(wèn)題規(guī)模： 算法求解的輸入量的多少，是問(wèn)題大小的本質(zhì)表示，一般用 n 表示
語(yǔ)句頻度（Frequency Count）： 一條語(yǔ)句的重復(fù)執(zhí)行次數(shù)
函數(shù)的漸近增長(zhǎng)
漸近增長(zhǎng)的函數(shù)： 輸入規(guī)模 n 在沒(méi)有限制的情況下，只要超過(guò)一個(gè)數(shù)值 N ，這個(gè)函數(shù)就總是大于另一個(gè)函數(shù)。給定兩個(gè)函數(shù) f(n) 和 g(n) ，如果存在一個(gè)整數(shù) N ，當(dāng) n > N 時(shí)， f(n) > g(n) 總成立，則 f(n) 的增長(zhǎng)漸近快于 g(n) 。
①我們可以忽略加法常數(shù)；
②與最高次項(xiàng)相乘的常數(shù)并不重要；
③最高次項(xiàng)的指數(shù)越大，函數(shù)增長(zhǎng)越快；
④判斷一個(gè)算法的效率時(shí)，函數(shù)的常數(shù)和其他次要項(xiàng)常常被忽略，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)。
某個(gè)算法，隨著問(wèn)題規(guī)模 n 的增大，它會(huì)越來(lái)越優(yōu)于另一個(gè)算法，或是越來(lái)越劣于另一個(gè)算法。
算法的時(shí)間復(fù)雜度的定義
為了客觀地反映一個(gè)算法的執(zhí)行時(shí)間，可以只用算法中的“基本語(yǔ)句”的執(zhí)行次數(shù)來(lái)度量算法的工作量。
基本語(yǔ)句： 指的是算法中 重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的語(yǔ)句 。
算法中基本語(yǔ)句重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模 n 的某個(gè)函數(shù) f(n) ， 算法的漸近時(shí)間復(fù)雜度 也被稱為 算法的時(shí)間量度 ，簡(jiǎn)稱 時(shí)間復(fù)雜度 記作： T(n)=O(f(n))
①其中 語(yǔ)句總的執(zhí)行次數(shù) T(n) 是關(guān)于問(wèn)題規(guī)模 n 的函數(shù)。
②其中數(shù)學(xué)符號(hào) “O” 表示 數(shù)量級(jí) 。
T(n)=O(f(n)) 表示了 隨問(wèn)題規(guī)模 n 的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率相同 ，也被稱作時(shí)間復(fù)雜度
算法的漸近時(shí)間復(fù)雜度 = 算法的時(shí)間量度 = 時(shí)間復(fù)雜度
像這樣用數(shù)學(xué)符號(hào) O 來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法，被稱為 大O記法
最優(yōu)算法： 隨著問(wèn)題規(guī)模 n 的增大， T(n) 增長(zhǎng)最慢的算法。
推導(dǎo)大 O 階方法
推導(dǎo)大 O 階：
- 用常數(shù) 1 取代語(yǔ)句頻度中所有的加法常數(shù)
- 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
- 如果最高階項(xiàng)存在且不是1，則去除所有與這個(gè)項(xiàng)相乘的常數(shù)
得到的結(jié)果就是大 O 階
以下是常見(jiàn)的時(shí)間復(fù)雜度：
最壞、最好和平均時(shí)間復(fù)雜度
對(duì)于某些問(wèn)題的算法，它的時(shí)間復(fù)雜度不僅僅與問(wèn)題的規(guī)模相關(guān)，還依賴于其他因素。
最好時(shí)間復(fù)雜度： 算法在最好情況下的時(shí)間復(fù)雜度，指的是算法計(jì)算量可能達(dá)到的最小值；
最壞時(shí)間復(fù)雜度： 算法在最壞情況下的時(shí)間復(fù)雜度，指的是算法計(jì)算量可能達(dá)到的最大值；
平均時(shí)間復(fù)雜度： 是所有情況中最有意義的，它是最期望的運(yùn)行時(shí)間，但是一般都是通過(guò)運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來(lái)的。
一般在沒(méi)有特殊說(shuō)明的情況下，都是指最壞時(shí)間復(fù)雜度。
算法空間復(fù)雜度
算法的漸近空間復(fù)雜度 = 算法所需存儲(chǔ)空間的量度 = 空間復(fù)雜度
算法的空間復(fù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法空間復(fù)雜度的計(jì)算公式為： S(n)=O(f(n))
一般情況下，一個(gè)程序在機(jī)器上執(zhí)行，除了需要存儲(chǔ)程序本身的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些 對(duì)數(shù)據(jù)進(jìn)行操作 的 輔助存儲(chǔ)空間 。其中，對(duì)于輸入數(shù)據(jù)所占的具體存儲(chǔ)量取決于問(wèn)題本身，與算法無(wú)關(guān)，這樣只需要分析該算法在實(shí)現(xiàn)時(shí)所需要的輔助空間即可。
若算法執(zhí)行時(shí)所需的輔助空間相對(duì)于輸入數(shù)據(jù)量是個(gè)常數(shù)，則稱此算法為 原地工作 ，空間復(fù)雜度 S(n)=O(1)
對(duì)于一個(gè)算法，時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的，好的時(shí)間復(fù)雜度往往會(huì)導(dǎo)致空間復(fù)雜度變壞，反之亦然。但由于內(nèi)存空間較為充足，所以一般首先考慮的是時(shí)間復(fù)雜度。
