數據結構和算法是壹名程序開發人員的必備基本功，所以需要我們平時不斷的主動去學習積累，接下來將自在文章中為大家具體介紹這兩個知識點，希望對大家有所幫助。
推薦課程：Python教程
引入概念
先來看壹道題:
如果 a+b+c=1000，且 a2+b2=c^2（a,b,c 為自然數），如何求出所有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**2 + b**2 == c**2 and a+b+c == 1000:
print("a, b, c: %d, %d, %d" % (a, b, c))
end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")運行結果：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 1066.117884
complete!運行時間竟然多達17.8分鐘
算法的提出
算法的概念
算法是計算機處理信息的本質，因為計算機程序本質上是壹個算法來告訴計算機確切的步驟來執行壹個指定的任務。壹般地，當算法在處理信息時，會從輸入設備或數據的存儲地址讀取數據，把結果寫入輸出設備或某個存儲地址供以後再調用。
算法是獨立存在的壹種解決問題的方法和思想。
對於算法而言，實現的語言並不重要，重要的是思想。
算法可以有不同的語言描述實現版本（如C描述、C++描述、Python描述等），我們現在是在用Python語言進行描述實現。
算法的五大特性
輸入: 算法具有0個或多個輸入
輸出: 算法至少有1個或多個輸出
有窮性: 算法在有限的步驟之後會自動結束而不會無限循環，並且每壹個步驟可以在可接受的時間內完成
確定性：算法中的每壹步都有確定的含義，不會出現二義性
可行性：算法的每壹步都是可行的，也就是說每壹步都能夠執行有限的次數完成
第二次嘗試
import time
start_time = time.time()
# 註意是兩重循環
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!")運行結果：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 0.632128註意運行時間0.632128秒
算法效率衡量
執行時間反應算法效率
對於同壹個問題，我們給出了兩種解決算法，在兩種算法的實現中，我們對程序執行的時間進行了測算，發現兩段程序執行的時間相差懸殊，由此我們可以得出壹個結論：實現算法程序的執行時間可以反映出算法的效率，即算法的優劣。
單靠時間值絕對可信嗎？
假設我們將第二次嘗試的算法程序運行在壹臺配置古老性能低下的計算機中，情況會如何？很可能運行的時間並不會比在我們的電腦中運行算法壹的時間快多少。
單純依靠運行的時間來比較算法的優劣並不壹定是客觀準確的！
程序的運行離不開計算機環境（包括硬件和操作系統），這些客觀原因會影響程序運行的速度並反應在程序的執行時間上。那麽如何才能客觀的評判壹個算法的優劣呢？
時間復雜度與“大O記法”
我們假定計算機執行算法每壹個基本操作的時間是固定的壹個時間單位，那麽有多少個基本操作就代表會花費多少時間單位。既然對於不同的機器環境而言，確切的單位時間是不同的，但是對於算法進行多少個基本操作(即花費多少時間單位)在規模數量級上卻是相同的，因此可以忽略機器環境的影響而客觀的反應算法的時間效率。
對於算法的時間效率，我們可以用“大O記法”來表示。
“大O記法”：對於單調的整數函數f，如果存在壹個整數函數g和實常數c>0，使得對於充分大的n總有f(n)<=c*g(n)，就說函數g是f的壹個漸近函數（忽略常數），記為f(n)=O(g(n))。也就是說，在趨向無窮的極限意義下，函數f的增長速度受到函數g的約束，亦即函數f與函數g的特征相似。
時間復雜度：假設存在函數g，使得算法A處理規模為n的問題示例所用時間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時間復雜度，簡稱時間復雜度，記為T(n)
如何理解“大O記法”
對於算法進行特別具體的細致分析雖然很好，但在實踐中的實際價值有限。對於算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數量的規模函數中那些常量因子可以忽略不計。例如，可以認為3n2和100n2屬於同壹個量級，如果兩個算法處理同樣規模實例的代價分別為這兩個函數，就認為它們的效率“差不多”，都為n2級。
最壞時間復雜度
分析算法時，存在幾種可能的考慮：
算法完成工作最少需要多少基本操作，即最優時間復雜度
算法完成工作最多需要多少基本操作，即最壞時間復雜度
算法完成工作平均需要多少基本操作，即平均時間復雜度
對於最優時間復雜度，其價值不大，因為它沒有提供什麽有用信息，其反映的只是最樂觀最理想的情況，沒有參考價值。
對於最壞時間復雜度，提供了壹種保證，表明算法在此種程度的基本操作中壹定能完成工作。
對於平均時間復雜度，是對算法的壹個全面評價，因此它完整全面的反映了這個算法的性質。但另壹方面，這種衡量並沒有保證，不是每個計算都能在這個基本操作內完成。而且，對於平均情況的計算，也會因為應用算法的實例分布可能並不均勻而難以計算。
因此，我們主要關註算法的最壞情況，亦即最壞時間復雜度。
時間復雜度的幾條基本計算規則
基本操作，即只有常數項，認為其時間復雜度為O(1)
順序結構，時間復雜度按加法進行計算
循環結構，時間復雜度按乘法進行計算
分支結構，時間復雜度取最大值
判斷壹個算法的效率時，往往只需要關註操作數量的最高次項，其它次要項和常數項可以忽略
在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度
算法分析
第壹次嘗試的算法核心部分
or a in range(0, 1001):
for b in range(0, 1001):
for c in range(0, 1001):
if a**2 + b**2 == c**2 and a+b+c == 1000:
print("a, b, c: %d, %d, %d" % (a, b, c))時間復雜度：
T(n) = O(n * n * n) = O(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))時間復雜度：
T(n) = O(n * n * (1+1)) = O(n * n) = O(n?)由此可見，我們嘗試的第二種算法要比第壹種算法的時間復雜度好多的。
常見時間復雜度
執行次數函數舉例階非正式術語12O(1)常數階2n + 3O(n)線性階3n? +2n + 1O(n?)平方階5log2n+20O(logn)對數階2n+3nlog2n+19O(nlogn)nlogn階6n? +2n? +3n + 1O(n?)立方階2nO(2n)指數階
註意，經常將log2n（以2為底的對數）簡寫成logn
常見時間復雜度之間的關系
所消耗的時間從小到大
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)Python內置類型性能分析
timeit模塊
timeit模塊可以用來測試壹小段Python代碼的執行速度。
class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)Timer是測量小段代碼執行速度的類。
stmt參數是要測試的代碼語句（statment）
setup參數是運行代碼時需要的設置
timer參數是壹個定時器函數，與平臺有關。
timeit.Timer.timeit(number=1000000)
Timer類中測試語句執行速度的對象方法。number參數是測試代碼時的測試次數，默認為1000000次。方法返回執行代碼的平均耗時，壹個float類型的秒數。
list的操作測試
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))from timeit import Timer
t1 = Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "seconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "seconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "seconds")
# ('concat ', 1.7890608310699463, 'seconds')
# ('append ', 0.13796091079711914, 'seconds')
# ('comprehension ', 0.05671119689941406, 'seconds')
# ('list range ', 0.014147043228149414, 'seconds')pop操作測試
x = range(2000000)
pop_zero = Timer("x.pop(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
x = range(2000000)
pop_end = Timer("x.pop()","from __main__ import x")
print("pop_end ",pop_end.timeit(number=1000), "seconds")
# ('pop_zero ', 1.9101738929748535, 'seconds')
# ('pop_end ', 0.00023603439331054688, 'seconds')測試pop操作：從結果可以看出，pop最後壹個元素的效率遠遠高於pop第壹個元素
可以自行嘗試下list的append(value)和insert(0,value),即壹個後面插入和壹個前面插入？
list內置操作的時間復雜度
dict內置操作的時間復雜度
數據結構
概念
數據是壹個抽象的概念，將其進行分類後得到程序設計語言中的基本類型。如：int，float，char等。數據元素之間不是獨立的，存在特定的關系，這些關系便是結構。數據結構指數據對象中數據元素之間的關系。
Python給我們提供了很多現成的數據結構類型，這些系統自己定義好的，不需要我們自己去定義的數據結構叫做Python的內置數據結構，比如列表、元組、字典。而有些數據組織方式，Python系統裏面沒有直接定義，需要我們自己去定義實現這些數據的組織方式，這些數據組織方式稱之為Python的擴展數據結構，比如棧，隊列等。
算法與數據結構的區別
數據結構只是靜態的描述了數據元素之間的關系。
高效的程序需要在數據結構的基礎上設計和選擇算法。
程序 = 數據結構 + 算法
總結：算法是為了解決實際問題而設計的，數據結構是算法需要處理的問題載體
抽象數據類型(Abstract Data Type)
抽象數據類型(ADT)的含義是指壹個數學模型以及定義在此數學模型上的壹組操作。即把數據類型和數據類型上的運算捆在壹起，進行封裝。引入抽象數據類型的目的是把數據類型的表示和數據類型上運算的實現與這些數據類型和運算在程序中的引用隔開，使它們相互獨立。
最常用的數據運算有五種
插入
刪除
修改
查找
排序