数据结构与算法笔记（一）—— 引入概念、时间复杂度
一、前沿
我們為什么要學習數據結構和算法？
我們舉一個可能不太恰當的例子:
如果將最終寫好運行的程序比作戰場，我們碼農便是指揮作戰的將軍，而我們所寫的代碼便是士兵和武器。
那么數據結構和算法是什么? 答曰:兵法!
我們可以不看兵法在戰場上肉搏，如此，可能會勝利，可能會失敗。即使勝利，可能也會付出巨大的代價。我們寫程序亦然:沒有看過數據結構和算法，有時面對問題可能會沒有任何思路，不知如何下手去解決;大部分時間可能解決了問題，可是對程序運行的效率和開銷沒有意識，性能低下；有時會借助別人開發的利器暫時解決了問題，可是遇到性能瓶頸的時候，又不知該如何進行針對性的優化。
如果我們常看兵法，便可做到胸有成竹，有時會事半功倍!同樣，如果我們常看數據結構與算法，我們寫程序時也能游刃有余、明察秋毫，遇到問題時亦能入木三分、迎刃而解。
故，數據結構和算法是一名程序開發人員的必備基本功，不是一朝一夕就能練成絕世高手的。冰凍三尺非一日之寒,需要我們平時不斷的主動去學習積累。
二、數據結構
我們如何用Python中的類型來保存一個班的學生信息?如果想要快速的通過學生姓名獲取其信息呢?
實際上當我們在思考這個問題的時候，我們已經用到了數據結構。列表和字典都可以存儲一個班的學生信息，但是想要在列表中獲取一名同學的信息時，就要遍歷這個列表，其時間復雜度為O(n)，而使用字典存時，可將學生姓名作為字典的鍵，學生信息作為值，進而查詢時不需要遍歷便可快速獲取到學生信息，其時間復雜度為O(1)。
我們為了解決問題，需要將數據保存下來，然后根據數據的存儲方式來設計算法實現進行處理，那么數據的存儲方式不同就會導致需要不同的算法進行處理。我們希望算法解決問題的效率越快越好，于是我們就需要考慮數據究竟如何保存的問題，這就是數據結構。
在上面的問題中我們可以選擇Python中的列表或字典來存儲學生信息。列表和字典就是Python內建幫我們封裝好的兩種數據結構。
2.1、概念
數據是一個抽象的概念，將其進行分類后得到程序設計語言中的基本類型。如: int，float，char等。數據元素之間不獨立的，存在特定的關系，這些關系便是結構。數據結構指數據對象中數據元素之間的關系。
Python給我們提供了很多現成的數據結構類型，這些系統自己定義好的，不需要我們自己去定義的數據結構叫做Python的內置數據結構，比如列表、元組、字典。而有些數據組織方式，Python系統里面沒有直接定義，需要我們自己去定義實現這些數據的組織方式，這些數據組織方式稱之為Python的擴展數據結構，比如棧，隊列等。
2.2、算法與數據結構的區別
數據結構只是靜態的描述了數據元素之間的關系。
高效的程序需要在數據結構的基礎上設計和選擇算法。
程序 = 數據結構＋算法
總結：算法是為了解決實際問題而設計的，數據結構是算法需要處理的問題載體
2.3、抽象數據類型(Abstract Data Type)
抽象數據類型(ADT)的含義是指一個數學模型以及定義在此數學模型上的一組操作。即把數據類型和數據類型上的運算捆在一起，進行封裝。引入抽象數據類型的目的是把數據類型的表示和數據類型上運算的實現與這些數據類型和運算在程序中的引用隔開，使它們相互獨立。
最常用的數據運算有五種:
- 插入
- 刪除
- 修改
- 查找
- 排序
三、算法的提出
3.1、算法的概念
算法是計算機處理信息的本質，因為計算機程序本質上是一個算法來告訴計簿機確切的步驟來執行一個指定的任務。一般地，當算法在處理信息時，會從輸入設備或數據的存儲地址讀取數據，把結果寫入輸出設備或某個存儲地址供以后再調用。
算法是獨立存在的一種解決問題的方法和思想。
對于算法而言，實現的語言并不重要，重要的是思想。
算法可以有不同的語言描述實現版本(如C描述、C++描述、Python描述等），我們現在是在用Python語言進行描述實現。
3.2、算法的五大特性
四、算法效率衡量
我們先來看一道題：
如果a+b+c=1000，且 a^2 + b^2 =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('time:%d',(end_time-start_time)) #方法二 start_time = time.time() for a in range(0,1001):for b in range(0,1001):c = 1000-a-bif a**2+b**2==c**2:print('a,b,c: %d,%d,%d'%(a,b,c)) end_time = time.time() print('time:%d',(end_time-start_time))執行時間反應算法效率
對于同一問題，我們給出了兩種解決算法，在兩種算法的實現中，我們對程序執行的時間進行了測算，發現兩段程序執行的時間相差懸殊，由此我們可以得出結論：實現算法程序的執行時間可以反應出算法的效率，即算法的優劣。
單靠時間值絕對可信嗎?
假設我們將第二次嘗試的算法程序運行在一臺配置古老性能低下的計算機中，情況會如何?很可能運行的時間并不會比在我們的電腦中運行算法一的快多少。
單純依靠運行的時間來比較算法的優劣并不一定是客觀準確的!
程序的運行離不開計算機環境（包括硬件和操作系統)，這些客觀原因會影響程序運行的速度并反應在程序的執行時間上。那么如何才能客觀的評判一個算法的優劣呢?
4.1、時間復雜度與“大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)
4.2、如何理解“大o記法”
對于算法進行特別具體的細教分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數量的規模函數中那些常量因子可以忽略不計。例如，可以認為3n^2和 100n2屬于同一個量級，如果兩個算法處理同樣規模實例的代價分別為這兩個函數，就認為它們的效率“差不多"，都為n2級。
4.3、最壞時間復雜度
分析算法時，存在幾種可能的考慮：
- 算法完成工作最少需要多少基本操作，即最優時間復雜度
- 算法完成工作最多需要多少基本操作，即最壞時間復雜度
- 算法完成工作平均需要多少基本操作，即平均時間復雜度
對于最優時間復雜度，其價值不大，因為它沒有提供什么有用信息，其反映的只是最樂觀最理想的情況，沒有參考價值。
對于最壞時間復雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。
對于平均時間復雜度，是對算法的一個全面評價，因此它完整全面的反映了這個算法的性質。但另一方面，這種衡量并沒有保證，不是每個計算都能在這個基本操作內完成。而且，對于平均情況的計算，也會因為應用算法的實例分布可能并不均勻而難以計算。
因此，我們主要關注算法的最壞情況，亦即最壞時間復雜度。
4.3、時間復雜度的幾條基本計算規則
4.4、常見時間復雜度
注意：經常將log2 n(以2為底的對數）簡寫成logn
常見時間復雜度之間的關系
所消耗的時間從小到大：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n ) < O(n!) < O(n^n)
五、Python內置類型性能分析
5.1、timeit模塊
timeit模塊可以用來測試一小段Python代碼的執行速度。
class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)Timer是測量小段代碼執行速度的類。
參數：
- stmt：要測試的代碼語句(statment) ;
- setup：運行代碼時需要的設置；
- timer：一個定時器函數，與平臺有關。
Timer類中測試語句執行速度的對象方法。
參數：
- number：測試代碼時的測試次數，默認為1000000次。
返回值：
- 返回執行代碼的平均耗時，一個float類型的秒數。
5.2、list的操作時間復雜度
from timeit import Timerdef t1():li =[]for i in range(1000):li.append(i)def t2():li =[]for i in range(1000):li = li + [i]def t3():li =[i for i in range(1000)]def t4():li=list(range(1000))def t5():li=[]for i in range(1000):li.extend([i])timer1 = Timer("t1()", "from __main__ import t1") print("append: ",timer1.timeit(1000))timer2 = Timer("t2()","from __main__ import t2") print("+:",timer2.timeit(1000))timer3 = Timer("t3()","from __main__ import t3") print("[i for i in range]: ",timer3.timeit( 1000))timer4 = Timer("t4()","from __main__ import t4") print("list(range()):",timer4.timeit(1000))timer5 = Timer("t5()","from __main__ import t5") print("extend: ",timer5.timeit(1000))------------結果----------- append: 0.1197639 +: 1.3471121 [i for i in range]: 0.029948899999999945 list(range()): 0.012717199999999984 extend: 0.11237865.3、dict的操作時間復雜度
總結
以上是生活随笔為你收集整理的数据结构与算法笔记（一）—— 引入概念、时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 学习笔记（二十二）—— 了解进程和线程
- 下一篇： 数据结构与算法笔记（二）—— 顺序表