1.算法定義

算法(Algorithm)是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。

一個(gè)算法應(yīng)該具有以下七個(gè)重要的特征：

①有窮性(Finiteness)：算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止;

②確切性(Definiteness)：算法的每一步驟必須有確切的定義;

③輸入項(xiàng)(Input)：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸 入是指算法本身定出了初始條件;

④輸出項(xiàng)(Output)：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒 有輸出的算法是毫無意義的;

⑤可行性(Effectiveness)：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行 的操作步，即每個(gè)計(jì)算步都可以在有限時(shí)間內(nèi)完成(也稱之為有效性);

⑥高效性(High efficiency)：執(zhí)行速度快，占用資源少;

⑦健壯性(Robustness)：對(duì)數(shù)據(jù)響應(yīng)正確。

2. 時(shí)間復(fù)雜度

計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間,時(shí)間復(fù)雜度常用大O符號(hào)(大O符號(hào)(Big O notation)是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。更確切地說，它是用另一個(gè)(通常更簡(jiǎn)單的)函數(shù)來描述一個(gè)函數(shù)數(shù)量級(jí)的漸近上界。在數(shù)學(xué)中，它一般用來刻畫被截?cái)嗟臒o窮級(jí)數(shù)尤其是漸近級(jí)數(shù)的剩余項(xiàng);在計(jì)算機(jī)科學(xué)中，它在分析算法復(fù)雜性的方面非常有用。)表述，使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無窮時(shí)的情況。

大O，簡(jiǎn)而言之可以認(rèn)為它的含義是“order of”(大約是)。

無窮大漸近

大O符號(hào)在分析算法效率的時(shí)候非常有用。舉個(gè)例子，解決一個(gè)規(guī)模為 n 的問題所花費(fèi)的時(shí)間(或者所需步驟的數(shù)目)可以被求得：T(n) = 4n^2 - 2n + 2。

當(dāng) n 增大時(shí)，n^2; 項(xiàng)將開始占主導(dǎo)地位，而其他各項(xiàng)可以被忽略——舉例說明：當(dāng) n = 500，4n^2; 項(xiàng)是 2n 項(xiàng)的1000倍大，因此在大多數(shù)場(chǎng)合下，省略后者對(duì)表達(dá)式的值的影響將是可以忽略不計(jì)的。

數(shù)學(xué)表示掃盲貼 python算法表示概念掃盲教程

一、計(jì)算方法

1.一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。

一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)。

2.一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個(gè)函數(shù)f(n)，因此，算法的時(shí)間復(fù)雜度記做：T(n)=O(f(n))。隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率成正比，所以f(n)越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。

在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出T(n)的同數(shù)量級(jí)(它的同數(shù)量級(jí)有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n!)，找出后，f(n)=該數(shù)量級(jí)，若T(n)/f(n)求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n)=O(f(n))。

3.常見的時(shí)間復(fù)雜度

按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：

常數(shù)階O(1), 對(duì)數(shù)階O(log2n), 線性階O(n), 線性對(duì)數(shù)階O(nlog2n), 平方階O(n^2)， 立方階O(n^3),...， k次方階O(n^k), 指數(shù)階O(2^n) 。

其中，

1.O(n)，O(n^2)， 立方階O(n^3),...， k次方階O(n^k) 為多項(xiàng)式階時(shí)間復(fù)雜度，分別稱為一階時(shí)間復(fù)雜度，二階時(shí)間復(fù)雜度。。。。

2.O(2^n)，指數(shù)階時(shí)間復(fù)雜度，該種不實(shí)用

3.對(duì)數(shù)階O(log2n), 線性對(duì)數(shù)階O(nlog2n)，除了常數(shù)階以外，該種效率最高

Python常用算法學(xué)習(xí)基礎(chǔ)教程