算法一：概述
概述
1. 算法
算法algorithm，來自于數(shù)學領域。算法的種類也很多，有好有壞。我們用時間復雜度和空間復雜度來衡量一個算法的好壞。
算法在實際開發(fā)中主要用在下面：
- 運算：比如超大整數(shù)進行運算；
- 查找：搜索引擎搜索內容，以及數(shù)據(jù)庫查找
- 排序：各種排序算法
- 最優(yōu)決策
2. 數(shù)據(jù)結構
數(shù)據(jù)結構是數(shù)據(jù)的組織、管理和存儲格式，其使用目的是為了高效的訪問和修改數(shù)據(jù)。
數(shù)據(jù)結構的組成有下面幾種：
- 線性結構：最簡單的結構，包括數(shù)據(jù)、鏈表、棧、隊列、哈希表等。
- 樹：二叉樹、二叉堆。
- 圖：元素間多對多的關系，更復雜的一種數(shù)據(jù)結構。
時間復雜度
1. 概念
時間復雜度是用來評估一段算法執(zhí)行時間的長短。受運行環(huán)境和輸入規(guī)模的影響，代碼的絕對執(zhí)行時間是無法預估的，但我們卻可以預估代碼的基本操作執(zhí)行次數(shù)。假設輸入規(guī)模是n，那么會有一個函數(shù)T(n)來表示當前算法的執(zhí)行次數(shù)。
2. O(n)官方定義
若存在函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)為不等于0的常數(shù)，則稱f(n)是T(n)的同量級函數(shù)。記作T(n)=O(f(n))。O為算法的漸進時間復雜度。也被稱為大O表示法。
3. 舉例
- T(n)=3n，那么去掉最高階系數(shù)3之后的漸進時間復雜度就是O(n)。
- T(n)=5logn，去掉最高階系數(shù)5，T(n)=O(logn)
- T(n)=2，去掉最高階2，T(n)=O(1)
- T(n)=0.5n2+0.5n，還是以最高階為準，去掉系數(shù)之后就是T(n)=O(n2)。
空間復雜度
1. 概念
算法的執(zhí)行除了上面說的時間成本，還有空間成本。因為算法在執(zhí)行指令的過程中，需要存儲一些中間數(shù)據(jù)。存儲這部分數(shù)據(jù)的成本，稱之為空間成本。因為內存是優(yōu)先的，所以在時間復雜度相同的情況下，空間復雜度越小越好。
和時間復雜度一樣，我們也用O(n)來標示算法在執(zhí)行過程中占用的內存空間。
2. 常見的空間復雜度
常量空間：算法的存儲空間和輸入規(guī)模無關，那么空間復雜度記作O(1)。比如向字典中插入一個數(shù)據(jù)。
線性空間：算法分配的空間是一個線性集合，并且集合大小和輸入規(guī)模成n成正比。那么空間復雜度記作O(n)。
二維空間：比如一個二位數(shù)組，集合的長度和寬度都和輸入規(guī)模n成正比。記作O(n2)
-
遞歸空間：有一類比較特殊的程序，自己內部會調動自己，我們稱之為遞歸調用。
計算機在執(zhí)行程序的時候，會專門分配一塊內存，用來存儲方法調用棧。
方法調用棧分為進棧和出棧兩個行為：當進入一個新方法時會執(zhí)行進棧操作，方法執(zhí)行完再執(zhí)行出棧操作。
所以，執(zhí)行遞歸操作所需要的內存空間和遞歸的深度成正比。如果遞歸的深度是n，那么空間復雜度就是O(n)。
3. 時間和空間復雜度的取舍
在絕大多數(shù)時候，時間復雜度更重要，我們寧可多分配一些內存空間，也要提升程序的執(zhí)行速度。
數(shù)組
1. 基本介紹
(1) 對應的英文是array。有限個相同類型變量組成的有序集合。數(shù)組中的每一個變量成為元素。
(2) 數(shù)組在內存中是連續(xù)的。也就是說順序不能亂，而且也不能跳過某個存儲單元。
(3) 數(shù)組的下標從0開始，一直到長度-1的位置
2. 基本操作
(1) 讀取和更新元素
根據(jù)下標index，從數(shù)組中拿到該元素，直接取值和賦值就可以了。
(2) 插入元素
根據(jù)插入位置的不同，分為中間插入和尾部插入。
- 尾部插入：直接把元素放在數(shù)組最后空閑位置即可。
- 中間插入：稍微復雜一些，需要從數(shù)組尾部元素開始，一直到插入點index，依次向后挪一位。從而把待插入點的位置空出來，然后把元素插入進去。
(3) 超范圍插入（數(shù)組擴容）
上面說的插入元素，都是在插入后長度不超過數(shù)組原長度的情況下進行。但還有一種情況，就是插入元素后，導致數(shù)組長度超出之前的長度。這就需要對數(shù)組進行擴容。
擴容的方法很簡單，再創(chuàng)建一個新數(shù)組，長度是舊數(shù)組的2倍。然后把舊數(shù)組中的元素全部復制過來，就實現(xiàn)了數(shù)組擴容。
(4) 刪除元素
這個就簡單多了，把要刪除index后的元素，依次向前挪動一位就可以了。
3. 時間復雜度
(1) 插入元素：涉及到擴容和挪位兩部分，這兩部分的時間復雜度都是O(n)，所以插入的時間復雜度也是O(n)。
(2) 刪除元素：只有挪位的操作，時間復雜度是O(n)。
(3) 刪除時不記順序：有這么一種騷操作，在刪除一個元素的時候，后面的元素不進行挪位。而是直接把最后一個元素復制到被刪除的位置上，然后再把最后一個元素刪除掉。這樣的時間復雜度是O(1)，但代價是數(shù)組順序發(fā)生改變。一般不常用。
4. 數(shù)組的優(yōu)勢和劣勢
(1) 優(yōu)勢：高效的隨機訪問能力，只要給出下標，就能以常量的時間找到對應的元素。
(2) 劣勢：由于數(shù)組在內存中是連續(xù)存儲，所以插入和刪除元素，必然會帶動大量元素的移動，影響效率。
總結：數(shù)組適合讀操作多，寫操作少的情景。
鏈表
1. 基本介紹
(1) 物理上一種非順序，非連續(xù)的數(shù)據(jù)結構，由若干個節(jié)點組成。
(2) 第一個節(jié)點成為頭結點，最后一個節(jié)點成為尾節(jié)點。
(3) 單向鏈表：每個節(jié)點有兩部分構成：存放數(shù)據(jù)的變量data，指向下一個節(jié)點的指針next。單向鏈表只能通過一個節(jié)點找到它的下一個節(jié)點，卻不能找到上一個節(jié)點。
(4) 雙向鏈表：每個節(jié)點由三部分組成，除了data和next之外，還有一個指向上一個節(jié)點的prev指針。雙向鏈表中，我們可以通過prev來找到上一個節(jié)點。
(5) 數(shù)組在內存中是占用了一片連續(xù)完整的內存空間，而鏈表則是見縫插針。鏈表分布在內存中的不同位置，依靠next和prev來關聯(lián)起來。
2. 基本操作
(1) 查找節(jié)點
鏈表不能快速定位，只能從頭節(jié)點開始，依次next來查找給定的index。時間復雜度是O(n)
(2) 更新節(jié)點
主要還是查找的耗時，更新的過程和數(shù)組一樣。
(3) 插入節(jié)點
因為鏈表是不連續(xù)的，所以不需要像數(shù)組那樣考慮擴容。只要內存空間足夠，可以一直添加。根據(jù)插入位置的不同，分為下面三種情況：
- 尾部插入：把最后一個節(jié)點的next指向新節(jié)點即可。
- 頭部插入：把新節(jié)點的next指向原頭節(jié)點，再把新節(jié)點變?yōu)殒湵淼念^結點。
- 中間插入：同樣很簡單，先把插入點的前置節(jié)點的next指向新節(jié)點，然后再把新節(jié)點的next指向原插入的節(jié)點。
(4) 刪除節(jié)點
同樣根據(jù)刪除節(jié)點位置的不同分為下面幾種情況：
- 頭部刪除
- 中間刪除
- 尾部刪除
3. 時間復雜度
(1) 查找過程的時間復雜度是O(n)。
(2) 插入和刪除，如果不考慮查找的過程，那么單純操作的時間復雜度是O(1)。
4. 數(shù)組和鏈表對比
(1) 數(shù)組的優(yōu)勢是快速定位元素，適合讀操作多，寫操作少的情況。
(2) 鏈表的優(yōu)勢在于能靈活的插入和刪除元素，如果需要在尾部頻繁的插入、刪除元素，鏈表更合適。
棧和隊列
1. 物理結構和邏輯結構
(1) 物理結構是實實在在的結構。比如上面說的數(shù)組和鏈表都是內存中實實在在的存儲結構，所以屬于物理結構。
(2) 邏輯結構是抽象的概念，它依賴于物理結構而存在。比如后面說到的棧和隊列，他們的實現(xiàn)方式皆可以是數(shù)組也可以是鏈表。
2. 棧的Stack基本介紹
(1) 比如一個羽毛球筒，一端有底，一端有口。我們向里面放入羽毛球。那么就會出現(xiàn)先放入的最后拿出，后放入的先拿出。這就是典型的棧stack。
(2) 棧是一種線性結構，棧中的元素只能先入后出FILO（First In Last Out）。最先進入的元素是棧底，最后進入的是棧頂。
(3) 棧既可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。
3. 棧的基本操作
就兩種：入棧和出棧。
(1) 入棧Push：把一個元素放入棧中。只能從棧頂一側放入，新入棧的元素會成為新的棧頂。
(2) 出棧Pop：把元素從棧中彈出。只有棧頂?shù)脑夭旁试S出棧。如果要把棧中間的元素出棧，那么必須先讓棧頂?shù)脑匾来纬鰲２趴梢浴?/p>
4. 隊列Queue的基本介紹
(1) 類似于汽車排隊過隧道。一端進，一端出，方向不能改變。
(2) 隊列遵循的是先入先出FIFO（First In First Out）原則。隊列的出口端叫隊頭，隊列的入口端叫隊尾。
(3) 隊列的實現(xiàn)既可以用數(shù)組也可以用鏈表。
注意：在使用數(shù)組來實現(xiàn)的時候，要在數(shù)組最后多留一個空位，這個空位是隊尾。當新元素入隊的時候，直接放到這個隊尾就可以了。
5. 隊列的基本操作
(1) 入隊
如果是用數(shù)組實現(xiàn)，那么就把新元素放到隊尾空白位上。
(2) 出隊
把隊頭的元素移除隊列。只允許隊頭一側移除元素。出隊元素的后一個元素會成為新的隊頭。
(3) 循環(huán)隊列
1) 在用數(shù)組實現(xiàn)隊列的時候，會有這樣的問題：隨著出隊元素的增多，隊頭左側的空間就失去作用，隊列的容量也會越來越小。如果出隊和入隊頻繁的發(fā)生，一遍是數(shù)組開頭空出大量空閑位置，另一方面數(shù)組還在不斷擴容。
2) 這時候循環(huán)隊列就出現(xiàn)了。在標記好隊頭和隊尾元素的情況下，新插入的元素，優(yōu)先去占已經(jīng)移除隊列的坑。打破原有的存儲順序。讓數(shù)組的空間更加合理的利用起來。
6. 棧和隊列的應用
(1) 棧的應用
通常用于對“歷史”的回溯。比如從瀏覽網(wǎng)頁返回上一級，再返回上上級。
(2) 隊列的應用
通常用于對“歷史”的回放。比如多線程等等隊列，就要根據(jù)誰先加進來，誰先執(zhí)行。
(3) 雙端隊列
結合棧和隊列的特性：既可以先入先出，也可以后入先出。
散列表
1. 基本介紹
散列表也叫做哈希表hash table。這種數(shù)據(jù)結構提供了鍵key值value的映射關系。只要給出yigekey，就可以高效查找到它所匹配的value，時間復雜度接近于O(1)。
2. 哈希函數(shù)
(1) 在上面介紹的數(shù)據(jù)結構中，數(shù)組的查找效率最高。但是數(shù)組只能根據(jù)下標index進行查找，而散列表的key是字符串。所以我們需要一個中轉站，來將可以轉換為數(shù)組的index，這個中轉站就是哈希函數(shù)。
(2) 哈希函數(shù)在不同語言中的實現(xiàn)方式不一樣。
3. 散列表的寫操作
(1) 步驟
先通過哈希函數(shù)，把key轉換為index。然后看下數(shù)組在該下標的元素是否為空。如果為空就直接存入。如果不為空，那就是典型的哈希沖突了。
(2) 哈希沖突
隨著數(shù)據(jù)的增多，哈希沖突不可避免。所以我們必須要有解決方案。常用的有兩種：開放尋址法和鏈表法。
1) 開放尋址法：就是要插入的index被占用了，那么就去尋找其它沒被占用的index。比如依次向后查找。
2) 鏈表法：這是一個重點了，Java的HashMap使用的就是這種。
HashMap數(shù)組的元素不僅僅是一個Entry對象，還是一個鏈表的頭結點。每個Entry對象通過next指向她的下一個Entry節(jié)點。當新來的Entry映射到與之沖突的數(shù)組位置時，只要插入到對應的鏈表中即可。
4. 散列表的讀操作
讀操作和寫操作差不多。也是通過哈希函數(shù)從key得到index。然后去數(shù)組中取值。如果對應index元素的key和要查找的key一直，那么直接取值即可。如果不一直，那么就查找該index開頭的鏈表。在該鏈表中依次查找key相同的就可以了。
5. 散列表的擴容
(1) 散列是基于數(shù)組的，既然數(shù)組要擴容，那么散列也會遇到擴容的問題。
(2) 什么時候需要擴容
經(jīng)過多次元素插入，散列表達到一定的飽和度，key映射位置發(fā)生沖突的概率會逐漸提高。這樣一來，大量元素擁擠在相同的數(shù)組下標位置，行成很長的鏈表。對后續(xù)插入操作和查詢操作都有很大的影響。這個時候，就需要擴容了。
(3) JDK中HashMap影響擴容的兩個因素：
Capacity：當前HashMap的長度
-
LoadFactor：HashMap的負載因子，默認值是0.75f。
當HashMap滿足下面的條件時，就行需要進行擴容：
HashMap.size >= Capacity * LoadFactor```
(4) 擴容的過程
新建一個新的Entry數(shù)組，長度為原來的2倍。
重新Hash：遍歷原Entry數(shù)組，把所有的Entry重新hash到新數(shù)組中。經(jīng)過擴容，原本擁擠的散列表又會變得稀疏。以前的那些常常的鏈表也會小時很多。
