引子：在網(wǎng)上找到了一門基于python實現(xiàn)的數(shù)據(jù)結構與算法的課程（課程鏈接：https://www.bilibili.com/video/av21540971/?p=33）打毛，老師講課的思路非常清晰俩功，適合入門學習者參考。接下來的幾篇文章是對課堂筆記的整理熬甫，希望能夠幫助更多的讀者蔓罚。
1. 概念引入
先來看一道題：如果 a + b + c = 1000,且 a^2+b^2=c^2（a,b,c為自然數(shù)），如何求出所有a豺谈、b、c可能的組合厂榛？
1.1 第一次嘗試
以上代碼運行的結果：
1.2 算法的提出
1.2.1 算法的概念
算法是計算機處理信息的本質击奶，因為計算機程序本質是一個算法來告訴計算機確切的步驟來執(zhí)行一個指定的任務责掏。一般地，當算法在處理信息時痰驱，會從輸入設備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)，把結果寫入輸出設備或某個存儲地址供以后再調用萄唇。
算法是獨立存在的一種解決問題的方法和思想另萤。
對于算法而言，實現(xiàn)的語言并不重要四敞，重要的是思想拔妥。
算法可以有不同的語言描述實現(xiàn)版本（如C描述、C++描述铺厨、Python描述等）硬纤，我們現(xiàn)在是在用Python語言進行描述實現(xiàn)。
1.2.2 算法的五大特征
1.輸入：算法具有0個或多個輸入
2.輸出：算法至少有1個或多個輸出
3.有窮性：算法在有限的步驟之后會在自動結束而不會無限循環(huán)洼裤，并且每一個步驟可以在可接受的時間內完成
4.確定性：算法中的每一步都有確定的含義溪王，不會出現(xiàn)二義性
5.可行性：算法的每一步都是可行的，也就是說每一步都能夠執(zhí)行有限的次數(shù)完成
1.3 第二次嘗試
在第一次嘗試的時候移国，我們將c作為一個獨立的變量并進行循環(huán)，這樣就一共有三層循環(huán)桥狡，所以造成了計算時間比較長皱卓。實際上，隨著a和b的確定嫂易，c值就已經(jīng)確定了掐禁，因此我們可以用 1000 - a - b 來替換 c 颅和，這樣就省去了一層循環(huán)峡扩，代碼如下：
上面代碼運行的結果：
可以發(fā)現(xiàn)障本，相較于第一次嘗試的運行結果，這次的運行時間明顯縮短了很多案训。
1.4 算法效率衡量
1.4.1 執(zhí)行時間反應算法效率
對于同一問題粪糙，我們給出了兩種解決算法，在兩種算法的實現(xiàn)中城舞，我們對程序執(zhí)行的時間進行了測算寞酿，發(fā)現(xiàn)兩段程序執(zhí)行的時間相差懸殊，由此我們可以得出結論：實現(xiàn)算法程序的執(zhí)行時間可以反應出算法的效率熟嫩，即算法的優(yōu)劣。
1.4.2 單靠時間值絕對可信嗎椅邓？
假設我們將第二次嘗試的算法程序運行在一臺配置古老性能低下的計算機中昧狮，情況會如何？很可能運行的時間并不會比在我們的電腦中運行的算法一快多少合住。因此撒璧，單純依靠運行的時間來比較算法的優(yōu)劣并不一定是客觀準確的！程序的運行離不開計算機環(huán)境（包括硬件和操作系統(tǒng)）卿樱，這些客觀原因會影響程序運行的速度并反應在程序的執(zhí)行時間上。那么如何才能客觀的評判一個算法的優(yōu)劣呢萨蚕？
1.4.3 時間復雜度與“大O記法”
我們假定計算機執(zhí)行算法每一個基本操作的時間是固定的一個時間單位，那么有多少個基本操作就代表會花費多少時間單位岳遥。算法對于不同的機器環(huán)境而言，確切的單位時間是不同的派继，但是對于算法進行多少個 基本操作（即花費多少時間單位）在規(guī)模數(shù)量級上卻是相同的妻往，由此可以忽略機器環(huán)境的影響而客觀的反應算法的時間效率试和。對于算法的時間效率，我們可以用“大O記法”來表示好渠。
“大O記法”：對于單調的整數(shù)函數(shù)f节视，如果存在一個整數(shù)函數(shù)g和實數(shù)常數(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)
1.4.4 如何理解“大O記法”
對于算法進行特別具體的細致分析雖然好，但在實踐中的實際價值有限逻谦。對于算法的時間性質和空間性質，最重要的是其數(shù)量級和趨勢贱鼻，這些是分析算法效率的主要部分。而計量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計邻悬。例如，可以認為和
同屬一個量級父丰，如果兩個算法處理同樣規(guī)模實例的代價分別為這兩個函數(shù)掘宪，就認為他們的效率“差不多”，都為
級镀首。
1.4.5 最壞時間復雜度
分析算法時鼠次，存在幾種可能的考慮：
算法完成工作最少需要多少基本操作，即最優(yōu)時間復雜度
算法完成工作最多需要多少基本操作竖瘾，即最壞時間復雜度
算法完成工作平均需要多少基本操作，即平均時間復雜度
對于最優(yōu)時間復雜度捕传，其價值不大扩劝，因為它沒有提供什么有用信息，其反映的只是最樂觀最理想的情況聂示，沒有參考價值簇秒。對于最壞時間復雜度，提供了一種保證，表明算法在此種程度是基本操作中一定能完成工作锋边。對于平均時間復雜度编曼，是對算法的一個全面的評價，因此它完整全面的反映了這個算法的性質往扔。但另一方面熊户，這種衡量并沒有保證，不是每個計算都能在這個基本操作內完成嚷堡。而且，對于平均情況的計算绿饵，也會因為應用算法的實例分布可能并不均勻而難以計算瓶颠。因此刺桃，我們主要關注算法的最壞情況，亦即最壞時間復雜度瑟慈。
1.4.6 時間復雜度的幾條基本計算規(guī)則
1. 基本操作，即只有常數(shù)項借杰，認為其時間復雜度為O(1)
2. 順序結構进泼，時間復雜度按加法進行計算
3. 循環(huán)結構，時間復雜度按乘法進行計算
4. 分支結構绞惦，時間復雜度取最大值
5. 判斷一個算法的效率時。往往只需要關注操作數(shù)量的最高次項济蝉，其它次要項和常數(shù)項可以忽略
6. 在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度
1.5 算法分析
第一次嘗試的算法核心部分
時間復雜度： T(n) = O(n*n*n) = O()
第二次嘗試的算法核心部分
時間復雜度： T(n) = O(n*n*(1+1)) = O(n*n) = O()
由此可見贺嫂，我們嘗試的第二種算法要比第一種算法的時間復雜度好多了涝婉。
1.6 常見時間復雜度
1.6.1 常見時間復雜度對比
1.6.2 常見時間復雜度之間的關系
所消耗時間從小到大? ?O(1) < O(logn) < O(n) < O(nlogn) < O() < O(
) < O(
) < O(n!) < O(
)
1.7 數(shù)據(jù)結構
我們如何用Python中的類型來保存一個班的學生信息墩弯？如果想要快速的通過學生姓名獲取其信息呢寞射？
實際上當我們在思考這個問題的時候，我們已經(jīng)用到了數(shù)據(jù)結構桥温。列表和字典都可以存儲一個班的學生信息，但是想要在列表中獲取一名同學的信息時旺韭，就要遍歷這個列表掏觉，其時間復雜度為O(n)，而使用字典存儲時澳腹，可將學生姓名作為字典的鍵，學生信息作為值沥邻，進而查詢時不需要遍歷便可以快速獲取到學生的信息羊娃，其時間復雜度為O(1)。
我們?yōu)榱私鉀Q問題蕊玷，需要將數(shù)據(jù)保存下來，然后根據(jù)數(shù)據(jù)的存儲方式來設計算法實現(xiàn)進行處理近弟，那么數(shù)據(jù)的存儲方式不同就會導致需要不同的算法進行處理挺智。我們希望算法解決問題的效率越快越好窗宦，于是我們就需要考慮數(shù)據(jù)究竟如何保存的問題二鳄，這就是數(shù)據(jù)結構。
在上面的問題中我們可以選擇Python中的列表或字典來存儲學生信息髓窜。列表和字典就是Python內建幫我們封裝好的兩種數(shù)據(jù)結構欺殿。
1.7.1 概念
數(shù)據(jù)是一個抽象的概念，將其進行分類后得到程序設計語言中的基本類型脖苏。如：int，float恃鞋，char等。數(shù)據(jù)元素之間不是獨立的恤浪，存在特定的關系肴楷，這些關系便是結構。數(shù)據(jù)結構指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關系绷杜。Python給我們提供了很多現(xiàn)成的數(shù)據(jù)結構類型直秆，這些系統(tǒng)自己定義好的，不需要我們自己去定義的數(shù)據(jù)結構叫Python的內置數(shù)據(jù)結構瑰剃，比如列表筝野、元組、字典歇竟。而有些數(shù)據(jù)組織方式，Python系統(tǒng)里面沒有直接定義宝磨，需要我們自己去定義實現(xiàn)這些數(shù)據(jù)的組織方式，這些數(shù)據(jù)組織方式稱之為Python的擴展數(shù)據(jù)結構唤锉，比如棧、隊列等株憾。
1.7.2 算法與數(shù)據(jù)結構的區(qū)別
數(shù)據(jù)結構只是靜態(tài)的描述了數(shù)據(jù)元素之間的關系晒衩。高效的程序需要在數(shù)據(jù)結構的基礎上設計和選擇算法。程序 = 數(shù)據(jù)結構 + 算法
總結：算法是為了解決實際問題而設計的听系，數(shù)據(jù)結構是算法需要處理的問題載體
1.7.3 抽象數(shù)據(jù)類型（Abstract Data Type）
抽象數(shù)據(jù)類型（ADT）的含義是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作，即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起弃秆，進行封裝髓帽。引入抽象 數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開，使它們相互獨立郑藏。
最常用的數(shù)據(jù)運算有五種：插入、刪除拌牲、修改歌粥、查找、排序
2. 順序表
在程序中失驶，經(jīng)常需要將一組（通常是同為某個類型的）數(shù)據(jù)元素作為整體管理和使用，需要創(chuàng)建這種元素組擦耀，用變量記錄它們，傳進傳出函數(shù)等眷蜓。一組數(shù)據(jù)中包含的元素個數(shù)可能發(fā)生變化（可以增加或刪除元素）胎围。對于這種需求芹敌，最簡單的解決方案便是將這樣一組元素看成一個序列垮抗，用元素在序列里的位置和順序，表示實際應用中的某種有意義的信息液茎，或者表示數(shù)據(jù)之間的某種關系辞嗡。這樣的一組序列元素的組織形式，我們可以將其抽象為線性表续室。一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關系明郭。線性表是最基本的數(shù)據(jù)結構之一，在實際程序中非常廣泛晃择，他還經(jīng)常被用作更復雜的數(shù)據(jù)結構的實現(xiàn)基礎。根據(jù)線性表的實際存儲方式衬横，分為兩種實現(xiàn)模型：
順序表呻顽，將元素順序地存放在一塊連續(xù)的存儲區(qū)里斑匪，元素間的順序關系由它們的存儲順序自然表示盏浇。
鏈表，將元素存放在通過鏈接構造起來的一系列存儲塊中锄贷。
2.1 順序表的基本形式
圖a表示的是順序表的基本形式曼月，數(shù)據(jù)元素本身連續(xù)存儲柔昼，每個元素所占的存儲單元大小固定相同，元素的下標是其邏輯地址捕透，而元素存儲的物理地址（實際內存地址）可以通過存儲區(qū)的起始地址Loc() 加上邏輯地址（第i個元素）與存儲單元大胁晗簟（c）的乘積計算而得破喻，即：
Loc() = Loc(
) + c*i
故，訪問指定元素時無需從頭遍歷曹质，通過計算便可獲得對應地址擎场，其時間復雜度為O(1)。如果元素的大小不統(tǒng)一迅办，則須采用圖b的元素外置的形式，將實際數(shù)據(jù)元素另行存儲姨夹，而順序表中的各單元位置保存對應元素的地址信息（即鏈接）矾策。由于每個鏈接所需的存儲量相同，通過上述公式蝴韭，可以計算出元素鏈接的存儲位置，以后順著鏈接找到實際存儲的數(shù)據(jù)元素履磨。注意，圖b中的c不再是數(shù)據(jù)元素的大小剃诅，而是存儲一個鏈接地址所需的存儲量驶忌，這個量通常很小。圖b這樣的順序表也被稱為對實際數(shù)據(jù)的索引付魔，這是最簡單的索引結構。
2.2 順序表的結構與實現(xiàn)
2.2.1 順序表的結構
一個順序表的完整信息包括兩部分翻屈，一部分是表中的元素集合妻坝，另一部分是為實現(xiàn)正確操作而需記錄的信息惊窖，即有關表的整體情況的信息厘贼，這部分信息主要包括元素存儲區(qū)的容量和當前表中已有的元素個數(shù)兩項。
2.2.2 順序表的兩種基本實現(xiàn)方式
圖a為一體式結構盾计，存儲表信息的單元與元素存儲區(qū)以連續(xù)的方式安排在一塊存儲區(qū)里赁遗，兩部分數(shù)據(jù)的整體形成一個完整的順序表對象。一體式結構整體性強哭尝，易于管理。但是由于數(shù)據(jù)元素存儲區(qū)域是表對象的一部分材鹦，順序表創(chuàng)建后耕姊，元素存儲區(qū)就固定了。圖b為分離式結構茉兰，表對象里只保存與整個表有關的信息（即容量和元素個數(shù)），實際數(shù)據(jù)元素存放在另一個獨立的元素存儲區(qū)里坯约，通過鏈接與基本表對象關聯(lián)。
2.2.3 元素存儲區(qū)替換
一體式結構由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲在一起闹丐，所以若想更換數(shù)據(jù)區(qū)被因，則只能整體搬遷，即整個 順序表對象（指存儲順序表的結構信息的區(qū)域）改變了梨与。分離式結構若想更換數(shù)據(jù)區(qū)，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可航徙，而該順序表對象不變陷虎。
2.2.4 元素存儲區(qū)擴充
采用分離式結構的順序表，若將數(shù)據(jù)區(qū)更換為存儲空間更大的區(qū)域尚猿，則可以在不改變表對象的前提下對其數(shù)據(jù)存儲區(qū)進行了擴充，所有使用這個表的地方都不必修改伴榔。只要程序的運行環(huán)境（計算機系統(tǒng)）還有空閑存儲，這種表結構就不會因為滿了而導致操作無法進行踪少。人們把采用這種技術實現(xiàn)的順序表稱為動態(tài)順序表糠涛，因為其容量可以在使用中動態(tài)變化。
擴充的兩種策略
1. 每次擴充增加固定數(shù)目的存儲位置忍捡，如每次擴充增加10個元素位置，這種策略可稱為線性增長具篇。特點：節(jié)省空間，但是擴充操作頻繁驱显，操作次數(shù)多瞳抓。
2. 每次擴充容量加倍，如每次擴充增加一倍存儲空間挨下。特點：減少了擴充操作的執(zhí)行次數(shù)，但可能會浪費空間資源叙淌。以空間換時間，推薦的方式鹰霍。
2.3 順序表的操作
2.3.1 增加元素
如圖所示茵乱，為順序表增加新元素111的三種方式
a. 尾端加入元素，時間復雜度為O(1)
b. 非保序的加入元素（不常見）督勺，時間復雜度為O(1)
c. 保序的元素加入渠羞，時間復雜度為O(n)
2.3.2 刪除元素
a. 刪除表尾元素次询，時間復雜度為O(1)
b. 非保序的元素刪除（不常見）瓷叫，時間復雜度為O(1)
c. 保序的元素刪除，時間復雜度為O(n)
2.4 Python中的順序表
Python中的list和tuple兩種類型采用了順序表的實現(xiàn)技術摹菠，具有前面討論的順序表的所有性質。tuple是不可變類型蔽介，即不變的順序表糟需，因此不支持改變其內部狀態(tài)的任何操作，而其他方面洲押，則與list的性質類似。
2.4.1 list的基本實現(xiàn)技術
Python標準類型list就是一種元素個數(shù)可變的線性表杈帐，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序）累铅，而且還具有以下行為特征：
1. 基于下標（位置）的高效元素訪問和更新，時間復雜度應該是O(1)娃兽；為滿足該特征尽楔，應該采用順序表技術，表中元素保存在一塊連續(xù)的存儲區(qū)中阔馋。
2. 允許任意加入元素，而且在不斷加入元素的過程中勋眯，表對象的標識（函數(shù)ID得到的值）不變。為滿足該特征客蹋，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時的list對象的標識ID不變嚼酝，只能采用分離式實現(xiàn)技術竟坛。
在Python的官方實現(xiàn)中，list就是一種采用分離式技術實現(xiàn)的動態(tài)順序表担汤，這就是為什么用list.append(x) （或 list.insert(len(list),x)），即尾部插入）比在指定位置插入元素效率高的原因隅很。
在Python的官方實現(xiàn)中，list實現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時叔营，系統(tǒng)分配一塊能容納8個元素的存儲區(qū)所宰；在執(zhí)行插入操作（insert或append）時，如果元素存儲區(qū)滿就換一塊4倍大的存儲區(qū)仔粥。但如果此時的表已經(jīng)很大（目前的閾值為50000），則改變策略谭羔，采用加一倍的方法。引入這種改變策略的方式瘟裸，是為了避免出現(xiàn)過多空閑的存儲位置诵竭。
