學(xué)習(xí)：算法和時(shí)間復(fù)雜度算法什么是算法？
算法（）是指解題方案的準(zhǔn)確而完整的描述算法的時(shí)間復(fù)雜性tn，是一系列解決問(wèn)題的清晰指令算法的時(shí)間復(fù)雜性tn，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。
算法也可以說(shuō)是我們?yōu)榱私鉀Q問(wèn)題而編寫(xiě)的程序，它能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。
同一問(wèn)題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。
一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度、空間復(fù)雜度、正確性、可讀性、健壯性（容錯(cuò)性）這幾個(gè)方面來(lái)考慮。
算法的主要方法
在解決問(wèn)題時(shí)，采用的方法不同，可能會(huì)有多種不同的算法。常用解決問(wèn)題的方法有：
如何評(píng)價(jià)算法的優(yōu)劣呢？比較簡(jiǎn)單、直觀的評(píng)價(jià)方式就是 算法的運(yùn)行時(shí)間或占用的空間
時(shí)間復(fù)雜度算法運(yùn)行時(shí)間推導(dǎo)：求解步驟
1.找出算法中的基本語(yǔ)句：執(zhí)行次數(shù)最多的那條語(yǔ)句
2.計(jì)算基本語(yǔ)句執(zhí)行次數(shù)
3.推算執(zhí)行次數(shù)數(shù)量級(jí)：保證最高次項(xiàng)正確
4.用大O表示
計(jì)算法則常見(jiàn)復(fù)雜度
python">a = 1
b = a
c = b
執(zhí)行時(shí)間與問(wèn)題規(guī)模n無(wú)關(guān)，時(shí)間復(fù)雜度為常數(shù)階，記T(n)=O(1)
a = 0
b = 100
for i in range(n):
a += i
b -= i
執(zhí)行時(shí)間與問(wèn)題規(guī)模n相關(guān),執(zhí)行次數(shù)f(n)=2n+2,時(shí)間復(fù)雜度為線性階,記T(n)=O(n)
x = 0
y = 1
for i in range(n):
x += i
for j in range(n):
y *= j
執(zhí)行時(shí)間與問(wèn)題規(guī)模n相關(guān),執(zhí)行次數(shù)f(n)=n^2+2,時(shí)間復(fù)雜度為平方階,記T(n)=O(n^2)
i = 1
while i <= n:
i *= 2
執(zhí)行時(shí)間與問(wèn)題規(guī)模n相關(guān),執(zhí)行次數(shù)2^(f(n)-1)=n,時(shí)間復(fù)雜度為對(duì)數(shù)階,記T(n)=O(logn)
for j in range(n):
i = 1
while i <= n:
i *= 2
執(zhí)行時(shí)間與問(wèn)題規(guī)模n相關(guān),時(shí)間復(fù)雜度為線性對(duì)數(shù)階,記T(n)=O(nlogn)
對(duì)時(shí)間復(fù)雜度的分析并不復(fù)雜，需要多多練習(xí)
拓展：其他時(shí)間復(fù)雜度
遞歸算法的時(shí)間復(fù)雜度（ time ）：
總體時(shí)間復(fù)雜度O(每個(gè)遞歸函數(shù)時(shí)間復(fù)雜度T*depth遞歸深度)
最好情況時(shí)間復(fù)雜度（best case time ）：
算法在最好情況下執(zhí)行代碼的時(shí)間復(fù)雜度，運(yùn)行時(shí)間最短的情況
最壞情況時(shí)間復(fù)雜度（worst case time ）：
算法在最壞情況下執(zhí)行代碼的時(shí)間復(fù)雜度，運(yùn)行時(shí)間最長(zhǎng)的情況
平均時(shí)間復(fù)雜度（ case time ）：
代碼在所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值
均攤時(shí)間復(fù)雜度（ time ）：
在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低復(fù)雜度，個(gè)別情況是高復(fù)雜度且發(fā)生具有時(shí)序關(guān)系時(shí)，可以將個(gè)別高復(fù)雜度均攤到低復(fù)雜度上。