1. 入門(mén)篇
1.1. 數(shù)據(jù)結(jié)構(gòu)與算法的意義
我們的目的是建立時(shí)間復(fù)雜度筐眷、空間復(fù)雜度意識(shí)铐炫，寫(xiě)出高質(zhì)量的代碼垒手，能夠設(shè)計(jì)基礎(chǔ)架構(gòu)，提升編程技能倒信，訓(xùn)練邏輯思維科贬，積攢人生經(jīng)驗(yàn)，以此獲得工作回報(bào)鳖悠，實(shí)現(xiàn)你的價(jià)值榜掌，完善你的人生。
- 優(yōu)化代碼及設(shè)計(jì)架構(gòu)乘综，提升代碼性能（非功能性的需求）
- 看待問(wèn)題的深度憎账，解決問(wèn)題的角度
- 鍛煉大腦思考能力
1.2. 數(shù)據(jù)結(jié)構(gòu)與算法的重點(diǎn)
數(shù)據(jù)結(jié)構(gòu)：一組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
↑↓
算法：操作數(shù)據(jù)的一組方法
學(xué)習(xí)順序：
- 復(fù)雜度分析：衡量算法執(zhí)行效率
- 10個(gè)數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表卡辰、棧胞皱、隊(duì)列、散列表九妈、二叉樹(shù)反砌、堆、跳表允蚣、圖于颖、Trie樹(shù)
- 10個(gè)算法：遞歸、排序嚷兔、二分查找、搜索做入、哈希算法冒晰、貪心算法、分治算法竟块、回溯算法壶运、動(dòng)態(tài)規(guī)劃、字符串匹配算法
學(xué)習(xí)要點(diǎn)：
- 來(lái)歷
- 自身的特點(diǎn)
- 適合解決的問(wèn)題
- 實(shí)際的應(yīng)用場(chǎng)景
學(xué)習(xí)技巧：
- 將所學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法自己寫(xiě)一遍浪秘，適度刷題
- 多問(wèn)蒋情、多思考、多互動(dòng)
- 設(shè)立目標(biāo)耸携，打怪升級(jí)學(xué)習(xí)法
- 反復(fù)迭代棵癣，不斷沉淀
1.3. 復(fù)雜度分析
為什么需要復(fù)雜度分析？
分析夺衍、統(tǒng)計(jì)算法的執(zhí)行效率和資源消耗
事后統(tǒng)計(jì)方法：依賴(lài)測(cè)試環(huán)境且受數(shù)據(jù)規(guī)模影響
↓
大O復(fù)雜度表示法：
漸進(jìn)時(shí)間復(fù)雜度狈谊，代碼執(zhí)行時(shí)間（空間）隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)
賦值語(yǔ)句執(zhí)行1次，for循環(huán)的條件判斷語(yǔ)句執(zhí)行n次
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
時(shí)間復(fù)雜度量級(jí)：
時(shí)間復(fù)雜度類(lèi)型：
// 全局變量，大小為10的數(shù)組array河劝，長(zhǎng)度len壁榕，下標(biāo)i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往數(shù)組中添加一個(gè)元素
void add(int element) {
if (i >= len) { // 數(shù)組空間不夠了
// 重新申請(qǐng)一個(gè)2倍大小的數(shù)組空間
int new_array[] = new int[len*2];
// 把原來(lái)array數(shù)組中的數(shù)據(jù)依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array復(fù)制給array赎瞎，array現(xiàn)在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 將element放到下標(biāo)為i的位置牌里，下標(biāo)i加一
array[i] = element;
++i;
}
其中 len 初始值為 10 ，但隨著調(diào)用函數(shù)次數(shù) k 的增加务甥，數(shù)組不斷擴(kuò)大為 10·2k 二庵，可視為 n
最好時(shí)間復(fù)雜度
解：直接插入數(shù)據(jù)的情況即 O(1)最壞時(shí)間復(fù)雜度
解：數(shù)組滿后復(fù)制數(shù)組的情況即 O(n)平均時(shí)間復(fù)雜度 = 加權(quán)/期望時(shí)間復(fù)雜度 = 每種情況的執(zhí)行次數(shù) * 發(fā)生概率
解：n 種直接插入數(shù)據(jù)的情況， 1 種數(shù)組滿后復(fù)制數(shù)組的情況缓呛，等概率為 1/(n+1)
即 1 * 1/(n+1) + … 1 * 1/(n+1) + n * 1/(n+1) = O(1)均攤時(shí)間復(fù)雜度 = 極特殊的平均時(shí)間復(fù)雜度
攤還分析法：將較高時(shí)間復(fù)雜度那次操作的耗時(shí)催享，平攤到其他那些時(shí)間復(fù)雜度比較低的操作上
解：前 n 次插入數(shù)據(jù)至數(shù)組（O(1)），第 n+1 次復(fù)制數(shù)組哟绊，再插入數(shù)據(jù)（O(n)）因妙，O(1)出現(xiàn)的次數(shù)遠(yuǎn)大于O(n)的次數(shù)，均攤得O(1)
