一、算法的引入
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 為自然數(shù)），如何求出所有a、b、c可能的組合?可以用枚舉法，簡單，但是計算量大。需要用至少三個循環(huán)來完成。
import time
start = time.time()
for a in range(1001):
for b in range(1001):
for c in range(1001):
if a**2+b**2 == c**2 and a+b+c==1000:
print('a = %d,b = %d,c = %d'%(a,b,c))
end = time.time()
print('The time is %f seconds'%(end-start))
運行結果
a = 0,b = 500,c = 500
a = 200,b = 375,c = 425
a = 375,b = 200,c = 425
a = 500,b = 0,c = 500
The time is 1317 seconds
顯然，運行用了很長時間。其實，枚舉法也是一種算法，該算法的執(zhí)行次數(shù)為1000的三次方，效率很低。
算法的概念
算法是計算機處理信息的本質。算法是獨立存在的一種解決問題的方法和思想。算法的五大特性：輸入；輸出；有窮性；確定性；可行性。對上面程序可以進行一定優(yōu)化：
import time
start = time.time()
for a in range(1001):
for b in range(1001-a):
c = 1000 - a - b
if a**2+b**2 == c**2:
print('a = %d,b = %d,c = %d'%(a,b,c))
end = time.time()
print('The time is %f seconds'%(end-start))
運行結果
a = 0,b = 500,c = 500
a = 200,b = 375,c = 425
a = 375,b = 200,c = 425
a = 500,b = 0,c = 500
The time is 0.992053 seconds
顯然比上面的運行時間要短得多得多。可以大致得到一個結論：實現(xiàn)算法程序的執(zhí)行時間可以反應出算法的效率，計算法的優(yōu)劣。算法的效率衡量：執(zhí)行時間（在一定程度上）反映算法效率。但是并不是絕對的，由于：（1）測試結果非常依賴測試環(huán)境：硬件不同會對結果造成很大影響。（2）測試結果受數(shù)據(jù)規(guī)模和數(shù)據(jù)本身的影響較大：如對于排序，如數(shù)據(jù)本身是有序的，可能執(zhí)行時間就會相對較短，同時數(shù)據(jù)規(guī)模較小時，測試時間不一定能真實反映算法的性能。所以每臺機器執(zhí)行總時間不一定一致，但是執(zhí)行的基本運算的數(shù)量大體相同。
二、時間復雜度大O
第一個例子中，執(zhí)行的次數(shù)為：T = 1000 * 1000 * 1000 * 21000到2000時T = 2000 * 2000 * 2000 * 21000換成N時，T = n * n * n * 2 = n ^ 3 * 2 = f(n) * 2即T(n) = f(n) * 2T(n) = O(f(n))其中，n表示數(shù)據(jù)規(guī)模的大小，T(n)表示代碼執(zhí)行的時間，f(n)代表每行代碼的執(zhí)行次數(shù)總和，O表示T(n)與f(n)成正比。此即為大O時間復雜度表示法，不是代碼真正的執(zhí)行時間，而是代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，也叫漸進時間復雜度，簡稱時間復雜度。
三、時間復雜度分析
方法：
1.只關心循環(huán)執(zhí)行次數(shù)最多的一段代碼
def cal(n):
sum = 0
i = 1
for i in range(n+1):
sum += i
return sum
函數(shù)內部，前兩行是常量級的執(zhí)行時間，與n的大小無關，可忽略，關注循環(huán)次數(shù)最多的那一個即for循環(huán)，for循環(huán)執(zhí)行了n次，所以時間復雜度為O(n)。
2.加法原則
總復雜度等于量級最大的那段代碼的復雜度。
def cal(n):
sum = 0
i = 1
for i in range(100):
sum += i
for i in range(n+1):
sum += i
for i in range(n+1):
for i in range(n + 1):
pass
第一個for循環(huán)為常數(shù)循環(huán)，復雜度為O(1)，第二個for為單層循環(huán)，為O(n)，第三個for循環(huán)為雙層嵌套循環(huán)，時間復雜度為O(n^2)。如T(n) = max(O(1),O(n),O(n^2)) = O(n^2)。分析算法時，存在幾種可能：※最優(yōu)時間復雜度：最少需要多少基本操作li = [1,2,3,4,5]列表有序，則常數(shù)時間，O(1)。※平均時間復雜度：平均需要多少基本操作※最壞時間復雜度：最多需要多少基本操作列表無序時，時間復雜度與元素個數(shù)正相關，即O(n)。最優(yōu)時間復雜度和平均時間復雜度價值不大，未提供太多有用的信息，因此主要關注算法的最壞情況，亦即最壞時間復雜度。
四、常見的時間復雜度
O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(2^n)
列表比較：
執(zhí)行次數(shù)實例復雜度非正式術語10O(1)常數(shù)階3n+2O(n)線性階2n^2^+3n+1O(n^2^)平方階2log~2~n+10O(log~2~n)對數(shù)階2nlog~2~n+2n+3O(nlog~2~n)nlog~2~n階2^n^O(2^n^)指數(shù)階
繪圖說明：
各種時間復雜度圖形比較
再分析：
def cal(n):
for i in range(n):
for j in range(i):
print(i,j)
要計算1+2+3+…+(n-1)=n*(n-1)/2，所以也為O(n^2)。
五、Python內置類型性能分析
timeit模塊用來測試一段代碼的執(zhí)行時間：三個參數(shù)：stmt, setup, timer即class timeit.Timer(stmt='',setup='',timer='')Timer:測試小段代碼執(zhí)行時間的類;stmt:要測試的代碼語句;setup:運行代碼時需要的設置;timer:定時器參數(shù),與平臺有關。
#分析列表添加的執(zhí)行效率
from timeit import Timer
def test1():
l = []
for i in range(1000):
l = l + [i]
def test2():
l = []
for i in range(1000):
#末尾追加
l.Append(i)
def test3():
#列表推導式
l = [i for i in range(1000)]
def test4():
l = list(range(1000))
def test5():
l = []
for i in range(1000):
#從頭添加
l.insert(0,i)
#函數(shù)要加引號
t1 = Timer('test1()','from __main__ import test1')
print('add',t1.timeit(number=1000))
t2 = Timer('test2()','from __main__ import test2')
print('append',t2.timeit(number=1000))
t3 = Timer('test3()','from __main__ import test3')
print('list derivation',t3.timeit(number=1000))
t4 = Timer('test4()','from __main__ import test4')
print('list range',t4.timeit(number=1000))
t5 = Timer('test5()','from __main__ import test5')
print('insert',t5.timeit(number=1000))
打印
add 1.223421629
append 0.06038822500000007
list derivation 0.030709197000000188
list range 0.012542454999999952
insert 0.2713445080000001
易知，第一種方式最慢，insert()方法稍快，append()更快，其他的也較快。
六、數(shù)據(jù)結構的引入
數(shù)據(jù)存儲方式的不同，會導致需要不同的算法進行處理,其執(zhí)行效率也會不同。如在用Python中的類型來存儲一個班的學生信息時,可以考慮通過列表和字典兩種方式.在通過學生姓名獲取其信息時,如通過列表,則要遍歷這個列表,其時間復雜度為O(n)(假設學生規(guī)模為n)而通過字典存儲時,可以將學生姓名作為字典的鍵,學生信息作為值,進行查詢時不需要遍歷即可快速獲取到學生信息,時間復雜度為O(1).這說明數(shù)據(jù)存儲方式的不同的確會導致需要的算法不同,用算法解決問題的效率也會不同。數(shù)據(jù)是一個抽象的概念,將其分類后得到程序設計語言的基本類型，如常見的int、float、char等。數(shù)據(jù)元素之間不是獨立的，存在特定的關系，這些關系便是結構。定義：數(shù)據(jù)結構指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關系，即數(shù)據(jù)組織的方式。Python中，數(shù)據(jù)結構分為：內置數(shù)據(jù)結構：Python已經實現(xiàn)，不需要我們再去定義，如列表、元組、字典等；擴展數(shù)據(jù)結構：Python并未定義，需要我們自己去定義實現(xiàn)這些數(shù)據(jù)的組織方式，如棧、隊列等。程序 = 數(shù)據(jù)結構 + 算法總結：算法是為了解決實際問題而設計的，數(shù)據(jù)結構是算法需要處理問題的載體。抽象數(shù)據(jù)類型（ADT）：指一個數(shù)據(jù)類型以及定義在此數(shù)據(jù)模型上的一組操作，即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆綁在一起，進行封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開，使它們相互獨立。
