說明：以下內(nèi)容均參考：[美]Aditya Bhargava所著的《算法圖解》
第一種使用的算法：二分查找竞穷。
二分查找的基本思想：每次都將要查找的序列砍掉一半滑沧，從而砍完整個(gè)序列至多需要 次竞膳，我們說算法的復(fù)雜度是
。
注意：復(fù)雜度中的 指的都是
敲才。
注意：僅當(dāng)列表是有序列表的時(shí)候孤钦，二分查找才管用。
二分查找算法的代碼表示：
def binary_search(nums, target):
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (lo + hi) // 2 # 必須要取整肴茄，否則數(shù)組的索引會(huì)出錯(cuò)
if nums[mid] == target:
return mid
if nums[mid] < target:
# 這里的加1及后面的減1是為了避免lo和hi陷入某些數(shù)中出不去(比如lo=5, hi=6)
lo = mid + 1
else:
hi = mid - 1
return None
算法時(shí)間復(fù)雜度中的“線性時(shí)間”的意思是：算法的運(yùn)行時(shí)間與序列的長(zhǎng)度相同晌畅，序列有多長(zhǎng)，運(yùn)行時(shí)間就會(huì)有多長(zhǎng)寡痰。其時(shí)間復(fù)雜度表示為 抗楔。
二分查找的運(yùn)行時(shí)間為對(duì)數(shù)時(shí)間（ 時(shí)間）。其時(shí)間復(fù)雜度表示為
拦坠。
計(jì)算算法時(shí)間復(fù)雜度的目的在于知道算法運(yùn)行時(shí)間的增速连躏，即當(dāng)序列的長(zhǎng)度增加時(shí)，算法的運(yùn)行時(shí)間額外增長(zhǎng)得有多快贞滨。例如反粥，當(dāng)序列長(zhǎng)度由一個(gè)較小的值變?yōu)橐粋€(gè)較大的值時(shí)，線性時(shí)間復(fù)雜度的額外運(yùn)行時(shí)間增加的非常多，而對(duì)數(shù)時(shí)間額外增加的非常少（幾乎不受序列長(zhǎng)度的影響）才顿，而且序列長(zhǎng)度越長(zhǎng)，這種差別就越大尤蒿。因此時(shí)間復(fù)雜度在解決實(shí)際問題的過程中發(fā)揮著非常重要的作用郑气。
大 表示法指出了算法需要執(zhí)行的操作數(shù)（
可以理解為“Operation”），它指出了算法運(yùn)行時(shí)間的增速腰池，實(shí)際上計(jì)算的是操作數(shù)尾组。（算法的速度指的并非時(shí)間，而是操作數(shù)的增速示弓。在談?wù)撍惴ǖ乃俣葧r(shí)讳侨，我們說的是隨著輸入的增加，其運(yùn)行時(shí)間將以什么樣的速度增加奏属。）
大 表示法實(shí)際上指出的是最壞情況下的運(yùn)行時(shí)間跨跨，它規(guī)定了算法運(yùn)行時(shí)間的上限（比如，假設(shè)一個(gè)算法的運(yùn)行時(shí)間是
囱皿，此時(shí)我們說這個(gè)算法的運(yùn)行時(shí)間不可能超過
）勇婴。
常見的五大時(shí)間復(fù)雜度：
| 時(shí)間復(fù)雜度 | 運(yùn)行時(shí)間 | 例子 |
|---|---|---|
| 快 | 二分查找 | |
| 較快 | 簡(jiǎn)單查找 | |
| 慢 | 快速排序 | |
| 較慢 | 選擇排序 | |
| 非常慢 | 旅行商問題 |
常見大O運(yùn)行時(shí)間的圖示如圖1所示：
圖1：常見的大O運(yùn)行時(shí)間
排序算法的重要性（或者說為什么要學(xué)排序？為什么有那么多的排序算法嘱腥？）：因?yàn)楹芏嗨惴▋H在數(shù)據(jù)經(jīng)過排序后才管用（比如二分查找）耕渴。
計(jì)算機(jī)內(nèi)存的工作原理：（計(jì)算機(jī)就像是很多抽屜的集合體，每個(gè)抽屜都有地址齿兔。）當(dāng)我們需要將數(shù)據(jù)存儲(chǔ)到內(nèi)存時(shí)橱脸，便會(huì)請(qǐng)求計(jì)算機(jī)提供存儲(chǔ)空間，然后計(jì)算機(jī)給我們一個(gè)地址分苇。當(dāng)需要存儲(chǔ)多項(xiàng)數(shù)據(jù)時(shí)添诉，有兩種基本方式——數(shù)組和鏈表。
數(shù)組中的元素在內(nèi)存中是相連的组砚。數(shù)組的這個(gè)特點(diǎn)正是導(dǎo)致數(shù)組在添加新元素時(shí)處理速度慢的根本原因：若數(shù)組原來所在的地址對(duì)應(yīng)的內(nèi)存后面沒有多余的內(nèi)存可供新元素加入吻商，那么計(jì)算機(jī)就要為這個(gè)數(shù)組分配一個(gè)新的地址，以保證所有的元素都能緊密相連地放在內(nèi)存中糟红，此時(shí)艾帐，數(shù)組中原先已有的元素就要全部被搬到這個(gè)新的地址中。同理盆偿，若再向數(shù)組中添加新元素時(shí)柒爸，若原有內(nèi)存還不夠，則又要重新分配新地址并搬移原來的所有元素......因此事扭，數(shù)組在動(dòng)態(tài)添加新元素時(shí)會(huì)因?yàn)閮?nèi)存原因而嚴(yán)重影響速度捎稚。 解決這種問題的一種方法是：預(yù)先為數(shù)組分配足夠的內(nèi)存。但是這種方法有一個(gè)缺點(diǎn)：不知道要事先分配多少內(nèi)存。如果分配多了則會(huì)導(dǎo)致內(nèi)存浪費(fèi)今野，分配少了就又要重新分配地址葡公。
徹底解決這個(gè)問題的一種方法是鏈表。鏈表中的元素可存儲(chǔ)在內(nèi)存的任何地方：鏈表的每個(gè)元素都存儲(chǔ)了下一個(gè)元素的地址条霜，從而使一系列隨機(jī)的內(nèi)存地址串在一起催什。在鏈表中添加新元素很容易：只需將其放入內(nèi)存，并修改它前面的那個(gè)元素指向的地址宰睡。
數(shù)組和鏈表是優(yōu)勢(shì)互補(bǔ)的：鏈表的優(yōu)勢(shì)在插入元素方面（當(dāng)插入一個(gè)新元素時(shí)很方便）蒲凶，但鏈表的查找就顯得很不方便（當(dāng)我們要查找鏈表中的某個(gè)元素時(shí)，我們是無法直接找到該元素的位置的拆内，只能從鏈表的頭結(jié)點(diǎn)開始旋圆，依次訪問下一個(gè)節(jié)點(diǎn)，直到找到要找的元素麸恍，因此鏈表的查找會(huì)相當(dāng)費(fèi)時(shí)）灵巧； 而恰恰相反，數(shù)組的優(yōu)勢(shì)就在于查找元素（可以迅速地找到數(shù)組的任何元素）或南，但其缺點(diǎn)是插入元素較慢孩等。
當(dāng)需要在中間插入元素時(shí)，鏈表是更好的選擇采够。當(dāng)需要?jiǎng)h除元素時(shí)肄方，鏈表也是更好的選擇，因?yàn)橹恍枰薷那耙粋€(gè)元素指向的地址即可蹬癌。而使用數(shù)組時(shí)权她，刪除元素后，必須將后面的元素都向前移逝薪。
鏈表僅支持順序訪問（即從第一個(gè)元素開始逐個(gè)地讀取元素）隅要，而數(shù)組同時(shí)支持順序訪問和隨機(jī)訪問，因此數(shù)組的讀取速度更快董济。實(shí)際情況大多要求能夠隨機(jī)訪問步清，因此數(shù)組用的很多。
數(shù)組和鏈表操作的運(yùn)行時(shí)間如下：
| 操作 | 數(shù)組 | 鏈表 |
|---|---|---|
| 插入 | ||
| 讀取 | ||
| 刪除 |
選擇排序算法：
| 算法名稱 | 選擇排序 |
|---|---|
| 算法用途 | 排序 |
| 算法描述 | 首先遍歷列表虏肾，從中找出元素的最大值廓啊，然后將其添加到一個(gè)新列表中；然后再次遍歷剩余的列表封豪，找出元素第二大的值谴轮，將其按順序添加到新列表中；......直到所有元素被排成一個(gè)新的序列 |
| 時(shí)間復(fù)雜度 | 每次遍歷的時(shí)間復(fù)雜度依次為： |
使用遞歸的好處是可以讓程序更容易理解廓推；使用循環(huán)的好處是程序的性能可能更高。
每個(gè)遞歸函數(shù)都有兩部分：遞歸基和遞歸條件翩隧。遞歸基指的是函數(shù)什么時(shí)候不再調(diào)用自己受啥，遞歸條件是指函數(shù)調(diào)用自己。每個(gè)遞歸函數(shù)必須要有遞歸基鸽心，否則會(huì)形成死循環(huán)。
棧的彈出指的是刪除并讀取居暖。
棧的基本操作：壓入（在棧頂添加一個(gè)新的元素）和彈出（刪除并讀取棧頂元素）顽频。
每當(dāng)程序調(diào)用一個(gè)函數(shù)時(shí)，計(jì)算機(jī)都將為該函數(shù)調(diào)用分配一塊內(nèi)存太闺，而且該函數(shù)調(diào)用涉及到的所有變量的鍵和值也都將存儲(chǔ)到內(nèi)存中糯景； 如果在這個(gè)函數(shù)里又有新的函數(shù)被調(diào)用，則先前那個(gè)函數(shù)會(huì)成為棧底省骂，然后新來的這個(gè)函數(shù)被壓入棧頂蟀淮，并在棧頂保存新函數(shù)所涉及變量的鍵和值；如果又嵌套的有別的函數(shù)被調(diào)用钞澳，則重復(fù)此過程怠惶； 當(dāng)棧頂?shù)暮瘮?shù)執(zhí)行完時(shí)，計(jì)算機(jī)會(huì)將其從棧頂彈出（讀取并刪除）（每一次的return都相當(dāng)于是彈出操作）轧粟，然后前一個(gè)函數(shù)成為新的棧頂策治，當(dāng)其執(zhí)行完后再將其從棧頂彈出；如此直到棧被彈空兰吟，則所有函數(shù)執(zhí)行完畢通惫，程序返回最終結(jié)果。
棧的缺點(diǎn)：存儲(chǔ)詳盡的信息可能占用大量的內(nèi)存混蔼。每個(gè)函數(shù)調(diào)用都要占用一定的內(nèi)存履腋，如果棧很高，則意味著計(jì)算機(jī)存儲(chǔ)了大量函數(shù)調(diào)用的信息惭嚣。此時(shí)遵湖，可以考慮將遞歸換成循環(huán)來實(shí)現(xiàn)，或者使用尾遞歸（但并非所有的語言都支持尾遞歸）料按。
分而治之是一種通用的問題解決方法奄侠，它隸屬于遞歸式問題解決方法。當(dāng)面對(duì)一個(gè)問題束手無策時(shí)载矿，不妨考慮一下分而治之垄潮。
使用分而治之解決問題的過程包括兩個(gè)步驟：
（1）找出遞歸基烹卒，這個(gè)遞歸基必須盡可能簡(jiǎn)單；
（2）不斷將問題分解（或者說縮小規(guī)模）弯洗，直到符合遞歸基的要求旅急。
分治策略的關(guān)鍵是如何縮小問題的規(guī)模。
分而治之其實(shí)并不是解決問題的算法牡整，而是一種解決問題的思路藐吮。
快速排序使用了分治策略。
一個(gè) list A 和一個(gè)空的 list 相加逃贝，得到的結(jié)果仍為 list A：
[1, 2, 3] + [ ] = [1, 2, 3]
快速排序的代碼如下：
def quicksort(nums):
if len(nums) < 2:
return nums # 這是遞歸基：空的或只包含一個(gè)元素的數(shù)組是有序的
else:
pivot = nums[0] # 從nums中取出一個(gè)元素當(dāng)做比較的基準(zhǔn)
# 接下來將原數(shù)組分成兩部分谣辞，一部分是小于pivot的，另一部分是大于pivot的
# smaller和bigger至少是空列表
smaller = [i for i in nums[1:] if i <= pivot]
bigger = [i for i in nums[1:] if i > pivot]
return quicksort(smaller) + [pivot] + quicksort(bigger)
快速排序是最快的排序算法之一沐扳，其平均時(shí)間復(fù)雜度為 泥从，但在最壞情況下，其時(shí)間復(fù)雜度和選擇排序一樣沪摄，均為
躯嫉。
快速排序的性能嚴(yán)重依賴于每次選擇的基準(zhǔn)值 pivot。在最好情況下杨拐，快速排序的時(shí)間復(fù)雜度為 祈餐，這發(fā)生在每次選擇的基準(zhǔn)值都能將余下的數(shù)組二等分，這樣只需要
次就能將整個(gè)數(shù)組全部分完；而每次的排序操作耗時(shí)均為
，因此此時(shí)的時(shí)間復(fù)雜度為
沪斟； 而在最壞的情況下型雳，快速排序的時(shí)間復(fù)雜度將達(dá)到
，這發(fā)生在每次選擇的基準(zhǔn)值都是剩余數(shù)組的最小值或最大值，這樣每次只能減少數(shù)組的一個(gè)元素。如此一來，將需要 n 次才能將整個(gè)數(shù)組的長(zhǎng)度減為0芭逝，非常耗時(shí)，而每次排序的時(shí)間復(fù)雜度均為
渊胸，因此這種情況下的整體時(shí)間復(fù)雜度為
旬盯。對(duì)這一解釋的兩個(gè)很形象的圖示如圖 2 - 1 和圖 2 - 2 所示。
圖 2 - 1：最壞情況下的時(shí)間復(fù)雜度：
圖 2 - 2：最好情況下的時(shí)間復(fù)雜度：
字典的創(chuàng)建翎猛、添加與讀扰趾病：
# 創(chuàng)建一個(gè)字典(以下兩種方式等效)
book = dict()
book = {}
# 添加鍵值對(duì)
book['milk'] = 1.49
book['banana'] = 2.37
# 查找字典中的內(nèi)容
# 字典的查找時(shí)間是O(1)時(shí)間
print(book['banana'])
# 用get方法可以獲取字典中的內(nèi)容
re = book.get('milk') # get中傳入的是鍵，是string類型的值
字典的一種應(yīng)用案例是緩存切厘。緩存是一種常用的加速方式萨咳，所有大型網(wǎng)站都使用緩存，緩存的數(shù)據(jù)存儲(chǔ)在散列表中疫稿。當(dāng)需要提取緩存中的內(nèi)容時(shí)培他，需要將頁面的URL映射到頁面數(shù)據(jù)鹃两。服務(wù)器緩存的一種代碼示例如下所示：
cache = {}
def get_page(url):
if cache.get(url): # 這里用get而不是直接用cache[url]，是因?yàn)槲覀兩胁淮_定cache中有沒有url
return cache[url] # 返回緩存的數(shù)據(jù)
else:
data = get_data_from_server(url) # 如果url不在cache中舀凛，則讓服務(wù)器生成這個(gè)url對(duì)應(yīng)的頁面
cache[url] = data # 將服務(wù)器生成的內(nèi)容保存到緩存中以便后續(xù)查找時(shí)無需重復(fù)生成
return data
字典內(nèi)部的工作機(jī)理：
散列函數(shù)負(fù)責(zé)將不同鍵所對(duì)應(yīng)的值映射到不同的位置俊扳，但若不同鍵所對(duì)應(yīng)的值映射到了同一個(gè)位置，就會(huì)引發(fā)沖突猛遍。
解決沖突的一種方法是：在沖突的位置處存儲(chǔ)一個(gè)鏈表馋记。但這里邊存在的問題是：這些存儲(chǔ)的鏈表不能過長(zhǎng)，否則字典的速度將急劇下降懊烤。因此這對(duì)散列函數(shù)提出了很高的要求：散列函數(shù)要盡可能地將鍵均勻地映射到字典的不同位置梯醒，即要盡量避免沖突的發(fā)生。
在平均情況下腌紧，字典執(zhí)行各種操作的時(shí)間都為 冤馏。
被稱為常量時(shí)間，但常量時(shí)間并不意味著馬上寄啼，而是說不管散列表多大，所需的時(shí)間都相同代箭。
但在最壞情況下墩划，字典的所有操作（包括查找、插入和刪除）運(yùn)行時(shí)間均為 嗡综。
