演算法初步—基本的數據結構（java為例）

• 2019 年 10 月 5 日
• 筆記

　　最近搞演算法，覺得超級吃力的，一直以為數學好的，數學可以考試滿分，演算法一定沒什麼問題，賤賤地，我發現我自己想多了，還是自己的基礎薄弱吧，今天我來補補最基礎的知識。

　　演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規範的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間複雜度與時間複雜度來衡量。

　　最簡單的栗子，我們來計算1+2+3+4+…+100，我們逐個去算覺得好麻煩的。如果是加到200呢？加到500呢？這時就引出了我們的演算法，高中數學就說過這個玩意，等差數列，也就是Sn=a1*n+[n*(n-1)*d]/2，我們帶入公式來看一下。Sn = 1*100+ [(100*99)/2]

5050，應該和我們一個個來計算一樣的吧。這個簡單的栗子也就是我們的演算法（現實中沒有這麼簡單的），但從這個簡單的栗子我們可以得到我給們要給予100個數字，我們就要計算100次，給出101個數字就要計算101次，那麼我們給出n給數字也就是要計算n次啦

所以我們就說我們的時間複雜度為O(n)。這次我們又假如，我們去吃小龍蝦，我們吃掉第一隻小龍蝦需要1分鐘，吃第二隻需要兩分鐘，吃第三隻時候需要三分鐘，那麼我們吃掉n只龍蝦需要多久呢？我們根據推算可以知道，我們需要 (n2+n)/2。時間複雜度即為O(n

2)

　　這時我們也就得到了時間複雜度為，保留最高階，常數變為1的結論，去得出時間複雜度。

　　空間複雜度，也就是佔用記憶體的大寫啦，多次循環的時候，其實一直佔用記憶體的，一直沒有釋放的，只要指針還在，我們的記憶體就沒有釋放的。一般也用O(n)來表示，運行幾次就是幾啦，記得把變數算進去。

　　說好的說數據結構，提前說了時間複雜度和空間複雜度，其實沒有提前，說了這兩個概念，後面的很多也就很好理解了。

　　線型結構：數組和鏈表。

數組：

　　數組就像是訓練有素的士兵一樣，報數1，2，3….我們可以通過他們的角標，得到他們的值，在java里的代表就是array啦。（在這裡說一下，數據的操作一般都是增刪改查，我們干過web的都知道啦）

　　增：如果是尾部插入，直接給予新的角標，給予值就可以了，頭部新增，需要把所有元素向後移動，中間插入也是如此的，在這裡簡單的說一下擴容，數組的每次擴容的2倍的，例如我們第一次佔用4個單位，不夠用了，我們需要擴容，直接擴展到8位（即使用不完8位，也擴容到8位）時間複雜度O(n)。

　　刪：刪除也是如此，每次是需要移動剩餘元素的，時間複雜度即為O(n)

　　改：直接去改就可以啦，時間複雜度為O(1)

　　查：剛才我們說了，數組是有角標的，我們直接通過角標就可以得到他們了，所以時間複雜度為O(1)

說了這些我們得到了數組的查詢表現還是很好的。

鏈表：

　　剛才說的數組像士兵一樣，有著整齊的隊伍，那麼鏈表就像是地下黨一樣，只是單線聯繫，我只是知道我的下級是誰，不知道我們的組織里其他人。只是通過他們的next指針去得到下一項。

　　增：在這裡鏈表新增就簡單很多了，只要找到自己要放置的位置，把指針指向他，他的指針指向他的下級就可以了，也就是說時間複雜度為O(1)

　　刪：刪除也是如此的，我們刪掉了自己，把原來指向自己的指針調整到指向我們指針原來指向的位置就可以了，時間複雜度為O(1)

　　改：我們這裡提要的修改，都是指不考慮查過程消耗的所有，也就是我們找到直接改就可以啦，時間複雜度為O(n)

　　查：我們需要從大哥找起，問他你的下線是誰？不是我們要的，我們繼續詢問他的下級，所以時間複雜度為O(n)

———————華麗的分割線————————-

棧：

　　棧？可以理解為羽毛球桶吧。我們依次把每一個不同顏色的羽毛球裝在桶內，但是我們每次只能拿出最外面的那個羽毛球，也就是說，棧，後進先出。

　　這裡的棧主要操作就是入棧和出棧了，我們剛才也說了後勁先出，也就是說入棧和出棧只會影響到最後一個元素，不涉及其它元素的整體移動，時間複雜度為O(1)

隊列：

　　隊列就猶如隧道一樣吧，或者理解為二極體，只能單向通電，也就是只能單向通過，我們也就可以得知，隊列的數據一定是先進先出啦。

　　入隊和出隊，性質和棧基本都是一致的，唯一的就是先進先出。

　　隊列其實還有雙向隊列（可以兩頭操作）和優先隊列（自帶VIP光環）。

———————華麗的分割線————————-　　

哈希結構：（散列表）

　　哈希？可以理解為坐卧鋪火車吧，上車了（開始存），列車員會把我們的票換成他們的票（哈希函數執行），然後我們會到我們相應的鋪位，等待下車。也就是key，value的形式來存的，java帶表示HashMap，（jdk1.8里HashMap有新特性，以後會講到）

　　新增：總共分兩步，換票，上卧鋪。也就是我們拿到key值進行hash計算，然後得到所對應的的位置，存儲我們的值。

有時候會出現hash衝突的情況，我們一般用開放定址和鏈表來解決衝突，如果太多了，會擴容，和數組擴容性質差不多，也是2倍的擴容。

　　查：通過hash函數將key哈希過來，得到位置，找到我們的值，衝突了，會找他的鏈表。

結構我們今天先說這些，貌似這些應該是結構基礎的所有了吧。有遺漏的小夥伴可以提醒我一下，我不知道的，我去學習一下，再整理髮給大家。晚安。