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