一. 算法與數(shù)據(jù)結(jié)構(gòu)

• 算法：用系統(tǒng)的方法描述解決問題的策略機(jī)制

• 數(shù)據(jù)結(jié)構(gòu)：計(jì)算機(jī)存儲(chǔ)與組織數(shù)據(jù)的一種方式，可以用來高效地處理數(shù)據(jù)

• 程序：算法 + 數(shù)據(jù)結(jié)構(gòu)

• 評(píng)判標(biāo)準(zhǔn)：多快好?。ú樵兛?，省內(nèi)存）

二. 運(yùn)行時(shí)間表示

• 什么是大O表示法：
  • O（order of）
  • 執(zhí)行完成某項(xiàng)策略需要多少個(gè)步驟，可以使用大O表示法表示
• 常見的大O運(yùn)行時(shí)間：
  • O(log n)，也叫對(duì)數(shù)時(shí)間，二分查找，以2為底，想要的結(jié)果n為冪
  • O（n），線性時(shí)間
  • O（n*log n)， 快速排序
  • O(n^2) ，選擇排序
  • O（n!），旅行商問題
• 注意：
  • 算法的速度指的是操作數(shù)的增速（隨著輸入的增加，運(yùn)行時(shí)間以什么樣的速度增加），而非時(shí)間

三. 結(jié)構(gòu)

• 線性結(jié)構(gòu)
  • 給定起始索引并以固定的步長(zhǎng)表示的數(shù)據(jù)結(jié)構(gòu)。適合快速查找數(shù)（O(1)速度)
  • 中間插入數(shù)據(jù)緩慢（O（n））插入數(shù)據(jù)索引后面的數(shù)據(jù)需要重新計(jì)算索引。
  • 空間固定，當(dāng)需要擴(kuò)容的時(shí)候，會(huì)先擴(kuò)大為初始空間的兩倍，并將先前的數(shù)據(jù)拷貝到新的空間。
• 單鏈表
  • 給定起始索引，并且起始?jí)K的末尾指向下一個(gè)塊。查找數(shù)據(jù)比較緩慢，中間插入數(shù)據(jù)快速。
• 雙鏈表
  • 解決單鏈表的逆序查找問題，給定上一個(gè)數(shù)據(jù)的索引。查找數(shù)據(jù)緩慢，中間插入數(shù)據(jù)快速。
• 哈希表
  • 提供快速的插入操作和查找操作（O(1))
  • 利用建key的hash值，和固定空間的size取余后得到索引（無序）。并根據(jù)索引防止key,value值。
  • 哈希沖突
    • 線性探查
    • 二次探查
    • 線性表與鏈?zhǔn)奖斫Y(jié)合
    • 哈希擴(kuò)容-重哈希（Rehashing）
• 樹結(jié)構(gòu)
  • 包括節(jié)點(diǎn)和邊的層級(jí)結(jié)構(gòu)
    • 根節(jié)點(diǎn)(root): 樹的最上層的節(jié)點(diǎn)，任何非空的樹都有一個(gè)節(jié)點(diǎn)
    • 路徑(path): 從起始節(jié)點(diǎn)到終止節(jié)點(diǎn)經(jīng)歷過的邊
    • 父親(parent)：除了根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的上一層邊連接的節(jié)點(diǎn)就是它的父親(節(jié)點(diǎn))
    • 孩子(children): 每個(gè)節(jié)點(diǎn)由邊指向的下一層節(jié)點(diǎn)
    • 兄弟(siblings): 同一個(gè)父親并且處在同一層的節(jié)點(diǎn)
    • 子樹(subtree): 每個(gè)節(jié)點(diǎn)包含它所有的后代組成的子樹
    • 葉子節(jié)點(diǎn)(leaf node): 沒有孩子的節(jié)點(diǎn)成為葉子節(jié)點(diǎn)
  • 樹的遍歷
    • 廣度：一層一層的遍歷
    • 深度：先一枝遍歷完再遍歷另一枝
• 堆：完全二叉樹
  • 最大堆：對(duì)于非葉子節(jié)點(diǎn)，其存儲(chǔ)的值比它的葉子節(jié)點(diǎn)大，也就是說根節(jié)點(diǎn)的值最大
  • 最小堆：和最大堆相反，對(duì)于非葉子節(jié)點(diǎn)，其存儲(chǔ)的值比它的葉子節(jié)點(diǎn)小，也就是說根節(jié)點(diǎn)的值最小

四. 順序

• 先進(jìn)先出：隊(duì)列
• 后進(jìn)先出：棧
• 頭尾都能進(jìn)能出：雙端隊(duì)列

五. 遞歸與棧

• 遞歸
  • 基線條件，遞歸結(jié)束的條件
  • 壓棧，后進(jìn)先出

六. 查找

• 線性查找
  • 一個(gè)一個(gè)的排除下去
• 二分查找
  • 將排序后的數(shù)據(jù)按照索引進(jìn)行查找

七. 排序

• 冒泡排序
  • 通過將最大的數(shù)字排到最后，第二大的數(shù)字排到倒數(shù)第二的方式進(jìn)行排序（逐級(jí)比較）一次找一個(gè)數(shù)
  • 或者將最小的數(shù)字排到最后，第二小的數(shù)排到倒數(shù)第二的方式逐級(jí)比較排序
• 選擇排序
  • 每次選擇最小或者最大的值放在已排序的數(shù)的后面
• 插入排序
  • 將數(shù)據(jù)分為已排序和未排序兩部分，將未排序中的數(shù)值選擇一個(gè)和已排序的數(shù)據(jù)再進(jìn)行一次排序
• 歸并排序
  • 分成一個(gè)個(gè)的元素再進(jìn)行排序合并
• 快速排序
  • 分成以一個(gè)有序的元素并合并