算法的概念
算法是計算機處理信息的本質，因為計算機程序本質上是一個算法來告訴計算機確切的步驟來執(zhí)行一個指定的任務实抡。一般的欠母，當算法在處理信息時，會從輸入設備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)澜术，把結果寫入輸出設備或某個存儲地址以后再調用艺蝴。
算法是獨立存在的一種解決問題的方法和思想猬腰。
算法的五大特性
- 輸入：算法具有0個或者多個輸入
- 輸出：算法至少有1個或者多個輸出
- 有窮性：算法在優(yōu)先的步驟之后會自動結束而不會無限循環(huán)鸟废，并且每一步步驟可以在可接受的時間內完成。
- 確定性：算法的每一步都有確定的含義姑荷，不會出現(xiàn)二義性盒延。
- 可行性：算法的每一步都是可行的，也就是說每一步都是能夠執(zhí)行有限的次數(shù)完成鼠冕。
案例引入
如果 a+b+c=1000添寺，且 a2+b2=c^2（a,b,c 為自然數(shù)），如何求出所有a懈费、b计露、c可能的組合?
import time
start_time = time.time()
for a in range(0, 1001):
for b in range(0, 1001):
for c in range(0, 1001):
if a + b + c ==1000 and a ** 2 + b ** 2 == c ** 2:
print('a, b, c: %d, %d, %d' %(a, b, c))
end_time = time.time()
print('elapsed: %f' %(end_time - start_time))
print('complete!')
import time
start_time = time.time()
# 注意是兩重循環(huán)
for a in range(0, 1001):
for b in range(0, 1001-a):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print("a, b, c: %d, %d, %d" % (a, b, c))
end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")
算法效率衡量
執(zhí)行時間反映算法效率
實現(xiàn)算法程序的執(zhí)行時間可以反應出算法的效率，即算法的優(yōu)劣。
單純依靠運行的時間來比較算法的優(yōu)劣并不一定是客觀準確的票罐！
程序的運行離不開i計算機的環(huán)境（包括硬件和操作系統(tǒng)）叉趣，這些客觀原因會影響程序運行的速度并反應在程序的執(zhí)行時間上。
時間復雜度與“大O記法”
我們假定計算機執(zhí)行算法的每一個基本操作的時間是固定的一個時間單位该押，那么有多少個基本操作就會代表會花費多少時間單位疗杉。對于不同的機器環(huán)境而言，確切的單位時間不同的蚕礼，但是對于算法進行多少個基本操作（即花費多少時間單位）在規(guī)模數(shù)量級上確是相同的烟具，由此我們可以忽略機器環(huán)境的影響而客觀的反映算法的時間效率。
對于算法的時間效率奠蹬，用“大O記法”來表示朝聋。
“大O記法”：對于單調的整數(shù)函數(shù)f，如果存在一個整數(shù)函數(shù)g和實常數(shù)c>0,使得對于充分大的n總有f(n)<= c*g(n),就是說函數(shù)g是f的一個漸近函數(shù)（忽略常數(shù)）囤躁，記為f(n) = O(g(n)). 也就是說玖翅，在趨向無窮的極限意義下，函數(shù)f的增長速度受到函數(shù)g的約束割以，即函數(shù)f與函數(shù)g的特征相似金度。
時間復雜度：假設存在函數(shù)g，使得算法A處理規(guī)模為n的問題示例所用的時間為T(n) = O(g(n)), 稱O(g(n))為算法A的漸近的時間復雜度严沥，簡稱為時間復雜度猜极，記為T(n)
最壞時間復雜度
分析算法時，存在幾種可能的考慮
- 算法完成工作最少需要多少基本操作消玄，即最優(yōu)時間復雜度
- 算法完成工作最多需要多少基本操作跟伏，即最壞時間復雜度
- 算法完成工作平均需要多少基本操作，即平均時間復雜度
我們通常關注算法的最壞情況翩瓜，即最壞時間復雜度受扳。
時間復雜度的幾個基本計算規(guī)則
- 1基本操作，與數(shù)據(jù)規(guī)模（n）無關兔跌，即只有常數(shù)項勘高，認為其時間復雜度為0(1)
- 2順序結構，時間復雜度按加法進行計算
- 3循環(huán)結構坟桅，時間復雜度按乘法進行計算
- 4條件分支結構华望，時間復雜度取最大值
- 5判斷一個算法的效率時，往往最需要關注操作數(shù)量的最高次項仅乓，其他次要項和常數(shù)可以忽略
- 6在沒有特殊說明下赖舟，我們所分析的算法的時間復雜度都是指最壞時間復雜度
常見時間復雜度
