https://www.bilibili.com/video/BV1VC4y1x7uv?p=85

二、算法分析

2.2 什么是算法分析

• 大O表示法

  
  
  image.png

2.3 python數(shù)據(jù)結(jié)構(gòu)的性能

• 列表

  
  
  image.png

• 字典

  
  
  image.png

說一下list[index]的o(1)原理，dict是散列表形式，訪問函數(shù)是o(1)很容易理解。但實際上list的訪問函數(shù)我認(rèn)為也是一種“散列表”，或者直接是額外空間的賦值存在。即在原始的線性結(jié)構(gòu)（鏈表）外，為了能夠快速訪問（畢竟索引是最必須和高頻的函數(shù)）而采用了額外空間來加速訪問。一種簡單的形式就是，比如list[1]用node_1來賦值，list[n]用node_n來賦值，需要訪問時，直接去找node_index就可以了，這是最簡單的方式。（書上的實現(xiàn)形式并不是python真正的實現(xiàn)形式）

三、基本數(shù)據(jù)結(jié)構(gòu)類型

3.2 線性結(jié)構(gòu)

包括棧、隊列、雙端隊列和列表。
棧：先進(jìn)后出
隊列：先進(jìn)先出
雙端隊列：允許先進(jìn)先出\先進(jìn)后出，典型場景是回文詞判定
列表：這里考慮無序列表需要的方法：

• class node: node.getData, node.getNext, node.setData, node.setNext
• class unorderdlist: unorderdlist.add, 其他就是常規(guī)函數(shù)，isempty, search等。。

四、遞歸Recursion

4.2 什么是遞歸

遞歸三大定律

• 必須有基本結(jié)束條件
• 必須改變自己的狀態(tài)并向基本結(jié)束條件演進(jìn)
• 必須遞歸地調(diào)用自身

典型問題1：謝爾賓斯基三角

• 結(jié)束條件：剩余迭代次數(shù)>=1
• 演進(jìn)和遞歸調(diào)用：
  1、把中間的三角形剔除；2、把左邊三角形進(jìn)行迭代；3、把上邊三角形進(jìn)行迭代；4、把右邊三角形迭代

典型問題2：河內(nèi)塔問題

• 結(jié)束條件：小塔層數(shù)為1（只有一個圓盤）
• 演進(jìn)和遞歸調(diào)用：
  1、把底盤上面的小塔從起點移到中間點，小塔進(jìn)行迭代；2、把底盤從起點移到終點；
  3、把底盤上面的小塔從中間點移到終點，小塔進(jìn)行迭代

4.5 動態(tài)規(guī)劃

典型問題：硬幣找零
先說一下貪心算法：先找面值最大的硬幣，剩下的零散的余額再用剩下的面值最大的硬幣來找零。。顯然在此場景下不是最優(yōu)解
動態(tài)規(guī)劃本質(zhì)上是一個遞歸問題：

def recDC(coinValueList,change,knownResults):
    minCoins = knownResults[change]  #在此場景下，最大的次數(shù)就是余額本身，所以這里相當(dāng)于是賦的初值為最大值
    if change in coinValueList:
        knownResults[change] = 1
        return 1
    if minCoins < change:
        return minCoins
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recDC(coinValueList, change-i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins
        return minCoins

knownResults = list(range(64))
print(recDC([1,5,10,25],63,knownResults))

• 設(shè)定一個初始列表，來保存每一個值條件下的最優(yōu)解，初值設(shè)為最差解
• 依次對列表中的值進(jìn)行迭代，求解當(dāng)前值的最優(yōu)解：
  1、如果有一個明確的最優(yōu)解，那就是本身（此場景下就是對應(yīng)找零余額存在合適的硬幣）；
  2、 沒有最優(yōu)解，則求解依次減去之前的值，再用新值去求最優(yōu)解，并用最后的復(fù)合答案最優(yōu)解，依次迭代；
  3、完全迭代后，用最優(yōu)解中的最優(yōu)解作為當(dāng)前值的最優(yōu)解。。。

五、排序和搜索

5.2 搜索

• 順序搜索
  無序表直接進(jìn)行順序搜索，o(n)
• 二分搜索
  無序表可以先進(jìn)行排序（額外消耗），再進(jìn)行有序列表的搜索，o(logn)，在要進(jìn)行大量搜索的時候綜合效率最高。如果本身只執(zhí)行單次搜索，效果可能不如順序搜索

5.2.3 散列

• 槽
  散列表的每一個位置是槽
• 負(fù)載因子
  數(shù)據(jù)項個數(shù)/散列表大小
• 沖突
• 完美散列函數(shù)
  實際上并不需要完美散列函數(shù)，而是用解決沖突的辦法來合理利用槽
• 沖突解決方法
  線性探測：尋找開放地址，但容易產(chǎn)生集中趨勢，造成周邊一系列槽都被線性探測填充；
  二次探測法：不進(jìn)行線性探測，而是采用一個再散列函數(shù)來尋找新的槽
  鏈

5.3 排序

• 冒泡排序
  對列表相鄰兩項進(jìn)行比較，并交換順序確保后一項大于前一項，每一輪遍歷完成則有一個最大值排到最后的位置。o(n2)
• 選擇排序
  每遍歷一次只交換一次數(shù)據(jù)，即將最大項放到最后的位置。o(n2)
• 插入排序
  依次將列表前方進(jìn)行排序，然后將后一項插入到前方已排序好的列表中正確位置。o(n2)
• 希爾排序
  間隔插入排序，以插入排序為基礎(chǔ)。大致介于O(n)和O(n2)之間。
• 歸并排序
  分而治之，持續(xù)地將一個列表分成兩半。如果列表是空的或者
  只有一個元素，那么根據(jù)定義，它就被排序好了（最基本的情況）。如果列表里的元素超過一個，我們就把列表拆分，然后分別對兩個部分調(diào)用遞歸排序。一旦這兩個部分被排序好了，那么就是歸并好了。O(nlogn)，效率是最高的，但是需要額外的空間來進(jìn)行兩個歸并數(shù)組的比較。
• 快速排序
  同樣是分而治之，選擇一個中值，并確定好中值在列表中正確的位置；將中值的左列表和右列表進(jìn)行中值迭代排序。O(nlogn)~O(n2)之間，但不需要額外的存儲空間。

六、樹和樹算法

6.2 術(shù)語

• 節(jié)點：又可細(xì)分為根節(jié)點、子節(jié)點、葉節(jié)點（沒有子節(jié)點的節(jié)點）、父節(jié)點、兄弟節(jié)點
• 子樹
• 層數(shù)（根節(jié)點層數(shù)為0），高度（所有層數(shù)的最大值）
• 路徑、邊

6.4 嵌套列表來實現(xiàn)樹

myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]

image.png

所以對樹的class可以基于列表實現(xiàn)

6.7 樹的遍歷

• 前序遍歷：先根后左再右
• 中序遍歷：先左后根再右
• 后序遍歷：先左后右再根

image.png

遍歷的方式?jīng)Q定了讀樹的方式，比如上面這一棵解析樹，只有中序遍歷是對的，(7+3)*（5-2）

6.8 二叉堆/二叉樹（優(yōu)先隊列）

除了先進(jìn)先出、先進(jìn)后出、雙端隊列之外，二叉堆可以實現(xiàn)特定的優(yōu)先隊列先出。二叉樹的關(guān)鍵是保持根節(jié)點是最小值，但是對其他節(jié)點不進(jìn)行排序。
完全二叉樹，是指左子樹和右子樹相對平衡，最多只相差一層的二叉樹。
生成完全二叉樹的復(fù)雜度是o（n），理論上對列表進(jìn)行排序的復(fù)雜度是o（n2），但是二叉樹只是保持最小值在根節(jié)點，有點類似于在無序列表中尋找最小值的復(fù)雜度是o（n）。

6.9 二叉搜索樹/BTS搜索樹

定義:始終保持左節(jié)點<父節(jié)點<右節(jié)點
bts搜索樹在極端情況下就一棵樹到底，因此更廣泛采用平衡二叉樹

6.10 平衡二叉樹/AVL樹

AVL樹在生成樹的時候會引入平衡因子+旋轉(zhuǎn)的操作來使得整體始終保持平衡

image.png

七、圖和圖算法

7.2 概念

• 頂點
• 邊
• 權(quán)重
• 路徑
• 圈

7.3 實現(xiàn)形式

• 鄰接矩陣（稀疏度通常特別大）
• 鄰接表（更常用）

7.7 廣度優(yōu)先搜索（BFS）

詞梯問題：尋找由fool到sage最短的路徑

）

7.8 深度優(yōu)先搜索（DFS）

騎士周游問題（下圖并不代表實際問題）：

image.png

每個節(jié)點記錄兩個值：發(fā)現(xiàn)時間和結(jié)束時間，典型特性是返回時間更晚的（父節(jié)點）優(yōu)先級總是要高于返回時間更早的（子節(jié)點），所以要實現(xiàn)深度搜索（所有節(jié)點都必須覆蓋），就得先通過父節(jié)點，再通過子節(jié)點。。適用于各種需要優(yōu)先級排序的場景，比如制作一個煎餅

image.png

7.11 dijkstra（BFS）

對于需要考慮權(quán)重的廣度搜索問題，dijkstra算法：每一個節(jié)點記錄源節(jié)點到當(dāng)前節(jié)點的最短路徑

7.12 prim（DFS）

對于需要走遍所有節(jié)點，但是為了保證路徑代價最小的問題，prim算法：每一個節(jié)點記錄源節(jié)點到當(dāng)前已發(fā)現(xiàn)樹（包含多個已發(fā)現(xiàn)節(jié)點）的最短路徑。。。走到最后一個節(jié)點的時候，記錄的就是源節(jié)點要走遍所有節(jié)點所需要的代價。。（書中的圖不對，每個節(jié)點記錄的值仍然是dijkstra）