開篇詞
- 王爭自己的算法之路
- 基礎一定要牢固 那些看起來的新技術核心和本質都是當初學的那些東西
基礎知識就像一座大樓的地基 它決定了我們的技術高度 要想快速的做出點事情 前提條件一定是基礎能力過硬 “內功要到位” - 課程分為四個遞進的模塊
- 入門篇
- 基礎篇
- 高級篇
- 實戰(zhàn)篇
01為什么要學習數(shù)據(jù)結構和算法
- 要想通過大廠面試 前往別讓數(shù)據(jù)結構和算法拖了后腿
我們學任何知識都是了“用”的环鲤，是為了解決實際工作問題的 - 掌握數(shù)據(jù)結構和算法 不管對閱讀框架源碼還是理解其背后的設計思想都是非常有用的 業(yè)務開發(fā)工程師難道真的想做一輩子的CRUD boy嗎？
- 基礎架構研發(fā)工程師 寫出達到開源水平的框架才是目標
- 自己只要還有追求 不想別行業(yè)淘汰 那就不要寫湊活能用的代碼
掌握了數(shù)據(jù)結構與算法 你看待問題的深度解決問題的角度就會完全不一樣
02 如何抓住重點 系統(tǒng)高效地學習數(shù)據(jù)結果與算法
- 什么是數(shù)據(jù)結構 算法
數(shù)據(jù)結構就是指一組數(shù)據(jù)的存儲結構 算法就是操作數(shù)據(jù)的一組方法 - 數(shù)據(jù)結構是為算法服務的会放，算法要作用在特定的數(shù)據(jù)結構上
- 學習方法：
- 邊學邊練 適度刷題
- 多問 多思考 多互動
- 打怪升級學習法
給自己設置一個切實可行的目標 - 知識需要沉淀 不要想試圖一下子掌握全部
學習的過程是反復迭代，不點沉淀的過程
03 復雜度分析 如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗
原文作者認為：
復雜度分析是整個算法學習的精髓 只要掌握了它 數(shù)據(jù)結構和算法的內容就掌握了一半
- 事后統(tǒng)計法 先將數(shù)據(jù)跑一遍 然后統(tǒng)計監(jiān)控
- 測試結果依賴測試環(huán)境
- 測試結果受數(shù)據(jù)規(guī)模的影響較大
- 大O表示法
- 假設每行代碼的執(zhí)行時間都是一樣的
- 所有代碼的執(zhí)行時間T（n）與每行代碼的執(zhí)行次數(shù)成正比
- 大O時間復雜度實際上并不具體代表代碼真正的執(zhí)行時間讥裤，代表執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢饮潦，也叫漸進時間復雜度琐脏，簡稱時間復雜度。
- 加法法則
總的時間復雜度等于量級最大的那段代碼的時間復雜度 - 乘法法則
嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積 -
常見時間復雜度實例分析
常見時間復雜度實例分析 - O（1）
一般情況下吴裤，算法中不存在循環(huán)語句、遞歸語句溺健，即使有成千上萬的代碼其時間復雜度也是O（1） - O(logn) O(nlogn)
i=1;
while (i <= n)
{ i = i * 2
}
O(log2n)
log3n = log3 2 * log2 n
在采用大O標記復雜度的時候可以忽略系數(shù) 即O(Cf(n)) = O(f(n))所以O(log2n)等于O(log3n)麦牺。因此在對數(shù)階時間復雜度的標示方法里，我們忽略對數(shù)的“底”鞭缭，統(tǒng)一表示為O(logn)
- O(nlogn)
如果一段代碼的時間復雜度是O(logn)剖膳，循環(huán)N遍，那么時間復雜度就是O(nlogn) - O(m+n)
m和n是表示兩個的數(shù)據(jù)規(guī)模岭辣，無法事先評估m(xù)和n誰的量級大吱晒，所以就不能使用加法法則省略掉其中一個 -
空間復雜度
表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關系。
我們常見的空間復雜度就是 O(1)沦童、O(n)仑濒、O(n2 )，像 O(logn)偷遗、O(nlogn) 這樣的對數(shù)階復雜度平時都用不到墩瞳。
04 復雜度分析（下）淺析最好、最壞氏豌、平均喉酌、均攤時間復雜度
最好情況時間復雜度就是，在最理想的情況下執(zhí)行這段代碼的時間復雜度
最壞情況時間復雜度就是在最糟糕的情況下執(zhí)行這段代碼的時間復雜度
平均情況時間復雜度
- 要查找的變量x在數(shù)組的位置泵喘，有n+1種情況泪电，在數(shù)組的0～n-1位位置種和不在數(shù)組中。我們把每種情況下纪铺，需要查找遍歷的元素個數(shù)累計起來相速，然后除以n+1，就可以得到需要遍歷的元素個數(shù)的平均值
image.png
我們知道霹陡，時間復雜度的大O標記法中和蚪，可以忽略掉系數(shù)，低階烹棉，常量攒霹，咱們把剛剛這個公式簡化之后，得到的鎖屏鍵時間復雜度就是O（n）浆洗。
這個結論雖然是正確的催束，但是計算過程稍微有點問題。剛剛的n+1種情況伏社，出現(xiàn)的概率并不是一樣的抠刺。
我們知道塔淤，要查找的變量x，要么在數(shù)組里速妖，要么就不在數(shù)組里高蜂。這兩種情況對應的概率統(tǒng)計起來很麻煩，我們假設在數(shù)組中與不在數(shù)組中的概率都是1/2.另外要查找的數(shù)據(jù)出現(xiàn)在0～n-1中的任意位置的概率就是1/（2n）罕容。
所以我們前面的推導的最大問題就是沒有將各種情況發(fā)生的概率考慮進去备恤。如果我們把每種情況發(fā)生的概率也考慮也考慮進入，那么平均時間復雜度的計算過程就變成了：
image.png
這個值就是概率論中的加權平均值锦秒，也叫做期望值露泊，所以平均時間復雜度的全稱應該叫加權平均時間復雜度或者期望時間復雜度。
引入概率之后旅择，前面那段代碼的加權平均值為（3n+1）/4.用大O表示法來表示惭笑，去掉系數(shù)和常量，這段代碼的加權時間復雜度仍然是O（n）生真。
均攤時間復雜度
// array 表示一個長度為 n 的數(shù)組
// 代碼中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[I];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
這段代碼實現(xiàn)了一個往數(shù)組中插入數(shù)據(jù)的功能沉噩。當數(shù)組滿了之后，也就是代碼中的count == array.lenth 時汇歹，我們用for循環(huán)遍歷數(shù)組求和屁擅，并清空數(shù)組，將求和之后的sum值放到數(shù)組的第一個位置产弹，然后再將新的數(shù)據(jù)插入派歌。如果數(shù)組一開始就有空閑空間，則直接經數(shù)據(jù)插入數(shù)組痰哨。
- 最好情況
數(shù)組中有空閑空間胶果，我們只需要將數(shù)組插入到數(shù)組下標為count的位置就可以了，所以最好的時間復雜度為O（1）斤斧。 - 最壞的情況下早抠，數(shù)組中已經沒有空間了，我們需要先做一次數(shù)組的遍歷求和撬讽，然后將數(shù)組插入蕊连。最壞的情況時間復雜度為O（n）。
-
平均時間復雜度
O（1）
假設數(shù)組的長度時n游昼，根據(jù)數(shù)據(jù)插入的位置的不同甘苍，我們可以分為n中情況，每種情況的時間復雜度時O（1）烘豌。除此之外载庭，還有一種‘額外’的情況，那就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù)。這個時候的時間復雜度是O（n）囚聚。而且靖榕，這n+1種情況發(fā)生的概率一樣，都是1/（n+1）顽铸。所以茁计，根據(jù)加權平均的計算方法，我們求得的平均時間復雜度就是
image.png
每一次O（n）的插入操作谓松，都會跟著n-1次的O（1）的插入操作簸淀，所以把耗時多的那次操作均攤到接下來的n-1次耗時少的操作上，均攤下來毒返，這一組的操作的均攤時間復雜度就是O（1）。這就是均攤分析的大致思路舷手。
均攤時間復雜度應用場景比較特殊拧簸，不會經常遇到，應用場景：
對一個數(shù)據(jù)結構進行一組連續(xù)操作中男窟，大部分情況下時間復雜度都很低盆赤，只有個別情況下時間復雜度比較高，而且這些操作之間存在前后連貫的關系歉眷，這個時候我們可以將這一組操作放在一塊分析牺六，看是否能將較高時間復雜度的那次操作的耗時平攤到其他那些時間復雜度比較低的操作上。而且在能夠應用均攤時間復雜度分析的場合汗捡，一般均攤時間復雜度就等于最好情況時間復雜度
05 編程語言只數(shù)組從從0開始的原因
歷史原因：c語言是從0開始的 大部分語言都借鑒了c語言
尋址方便：
a[i] address = start + i *(date_type_size)
else
a[i] address = start + (i - 1) *(date_type_size)
06 鏈表：實現(xiàn)LRU緩存淘汰算法
- 線性表：數(shù)組 隊列 鏈表
- 非線性表： 樹 圖
