廢話時(shí)間：
算法實(shí)際上是高于語(yǔ)言的。
所以我是第一Ｎ肌０┭埂嫡霞！
比如說(shuō)你的列表.sort 它里面其實(shí)就是實(shí)現(xiàn)了一種算法衙荐。
算法：一個(gè)計(jì)算過(guò)程捞挥，解決問(wèn)題的方法。
程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法忧吟。
一：時(shí)間復(fù)雜度：用來(lái)評(píng)估算法運(yùn)行效率（時(shí)間）的一個(gè)式子砌函。
光年是距離。
一般來(lái)說(shuō)：時(shí)間復(fù)雜度高的算法比復(fù)雜度低的算法慢溜族。
? 問(wèn)題規(guī)亩锟。基本上差不多一樣的時(shí)候。即n
? 與機(jī)器有關(guān)煌抒。
? 時(shí)間復(fù)雜度是獨(dú)立于機(jī)器的仍劈。
常見(jiàn)的時(shí)間復(fù)雜度：
o(1) < o(logn) < o(n) < o(nlogn) < o(n的平方) < o(n平方logn) < o(n的三次方)
如何簡(jiǎn)單判斷時(shí)間復(fù)雜度？
最好是根據(jù)運(yùn)行過(guò)程來(lái)估計(jì)
找到代表問(wèn)題規(guī)模的n 魑魅魍魎chi‘mei’wang‘liang
如何一眼判斷時(shí)間復(fù)雜度寡壮？
是否有循環(huán)減半的過(guò)程 -> o(logn)
幾層循環(huán)就是n的幾次方的復(fù)雜度
二：空間復(fù)雜度
用來(lái)評(píng)估算法內(nèi)存占用大小的一個(gè)式子
-
空間換時(shí)間
例如：如果你想讓你的算法快點(diǎn)贩疙，就需要更多的緩存。
三：基本算法
算法里面重要的思想
遞歸的兩個(gè)特點(diǎn)：
- 調(diào)用自身
- 結(jié)束條件
def qq(n):
if n == 0 :
print('我的小可愛(ài)',end='')
else:
print('抱著',end='')
qq(n-1)
print('的我',end='')
qq(5)
# 抱著抱著抱著抱著抱著我的小可愛(ài)的我的我的我的我的我
def fun(x):
if x > 0:
print(x)
fun(x-1)
def func(x):
if x > 0:
func(x-1)
3.0 漢諾塔
當(dāng)n個(gè)盤(pán)子時(shí)况既，把n-1看做一部分这溅。
1. 把n-1個(gè)圓盤(pán)從a經(jīng)過(guò)c移動(dòng)到b
2. 把第n個(gè)圓盤(pán)從a移動(dòng)到c
3. 把n-1個(gè)圓盤(pán)從b經(jīng)過(guò)a移動(dòng)到c
t = 0
def hanoi(n,a,b,c):
global t
if n > 0:
hanoi(n-1,a,c,b)
t +=1
print(':moving from %s --> %s.'%(a,c))
hanoi(n-1,b,a,c)
hanoi(5,'a','b','c')
print('本次總共運(yùn)行 %s 次'%t)
漢諾塔移動(dòng)次數(shù)的遞推式：h(x) = 2h(x-1)+1
前部分算法分為兩部分：查找和排序
3.1 列表查找：從列表中查找指定元素
- 輸入：列表、待查找元素
- 輸出：元素下標(biāo)或未查找到元素
3.2 順序查找
- 從列表第一個(gè)元素開(kāi)始棒仍，順序進(jìn)行搜索悲靴，直到找到為止。
3.3 二分查找
- 從有序列表的候選區(qū)data[0:n]開(kāi)始莫其，通過(guò)對(duì)待查找的值和候選區(qū)中間值的比較癞尚，可以使候選區(qū)減少一半。
3.1 二分查找
-
使用二分查找來(lái)找3
1榜配，2否纬，3吕晌，4蛋褥，5，6睛驳，7烙心，8，9
-
Low high
- ? mid
如果high < low 乏沸，說(shuō)明你要找的值不存在淫茵。
def erfen_search(li,val):
low = 0
high= len(li) - 1
while low<=high:
mid = (low+high) // 2
if li[mid] == val:
return mid
elif li[mid] < val:
low = mid + 1
else:
high = mid - 1
a = erfen_search([1,2,3,4.123,123,12,3,12,3,12,3,21,3,213,21,321,3,213,21,321,3,21,4,3,543,53,45,435,342,5],435)
# 上面這個(gè)方法有問(wèn)題，不信你試蹬跃。
# 遞歸版本二分查找
def bin_search_rec(data_set,value,low,high):
if low <= high:
mid = (low + high) // 2
if data_set[mid] == value:
return mid
elif data_set[mid] < value:
low = mid + 1
return bin_search_rec(data_set,value,low,high)
else:
high = mid - 1
return bin_search_rec(data_set,value,low,high)
else:
return
列表排序
- 列表排序
- 將無(wú)序列表變?yōu)橛行蛄斜怼?.sort
- 應(yīng)用場(chǎng)景
- 各種榜單
- 各種表格
- 給二分查找用
- 給其他算法用
輸入：無(wú)序列表
輸出：有序列表
排序Low B三人組
- 冒泡排序
- 插入排序
- 選擇排序
算法關(guān)鍵點(diǎn)：
- 有序區(qū)
- 無(wú)序區(qū)
升序與降序
排序兇兇組：
- 快排
- 思路：
- 取一個(gè)元素p（第一個(gè)元素）匙瘪，使元素p歸位；
- 列表被p分成兩部分，左邊逗比p小丹喻，右邊逗比p大‘
- 遞歸完成排序薄货。 遞歸終止條件：列表剩一個(gè)元素。
- 算法關(guān)鍵點(diǎn)：1. 歸位 2. 遞歸
- 堆排
- 歸并排序
沒(méi)什么人用的排序：
- 基數(shù)排序
- 希爾排序
- 桶排序
總覽：
| 執(zhí)行次數(shù)函數(shù) | 階 | 非正式術(shù)語(yǔ) |
|---|---|---|
| 12 | O(1) | 常數(shù)階 |
| 2n+3 | O(n) | 線性階 |
| 3n2+2n+1 | O(n2) | 平方階 |
| 5log2n + 20 | O(logn) | 對(duì)數(shù)階 |
| 2n + 3nlog2n + 19 | O(nlogn) | nlogn階 |
| 6n3 + 2n2 + 3n +4 | O(n3) | 立方階 |
| 2" | O(2") | 指數(shù)階 |
