數據結構，演算法宏觀印象構建
- 2019 年 10 月 12 日
- 筆記
前言
這篇文章主要是鳥瞰數據結構和演算法，不涉及到具體的細節。
闡述邏輯通過黃金思維圈中的是什麼，為什麼展開。
內容包括：
什麼是數據結構
為什麼需要需要數據結構
數據結構分類
- 什麼是演算法
- 為什麼需要演算法
演算法的衡量標準
關於數據結構
什麼是數據結構？
- 邏輯結構：描述數據之間的關係
- 物理結構：描述數據存儲的方式
為什麼需要數據結構？
以有效的方式處理數據，主要體現在存儲和檢索方面。
數據結構的分類
邏輯結構
1，集合結構
例如一個集合中包含橘子，蘋果和香蕉。
集合具有三大特性：
- 唯一性
- 互斥性
- 無序性
2，線性結構
元素存在一對一的相互關係
3，樹形結構
元素存在一對多的相互關係
4，圖形結構
元素存在多對多的相互關係
物理結構
順序存儲
邏輯上相鄰的節點物理上也相鄰【查詢效率高，插入刪除效率低】
鏈式存儲
邏輯上相鄰的節點物理上不一定相鄰【插入刪除效率高，查詢效率低】
索引存儲
除建立存儲結點資訊外，還建立附加的索引表來標識結點的地址。
用結點的索引號來確定結點存儲地址，其優點是檢索速度快，缺點是增加了附加的索引表,會佔用較多的存儲空間。
散列存儲
又稱hash存儲。由節點的關鍵碼值決定節點的存儲地址。
散列是數組存儲方式的一種發展，相比數組，散列的數據訪問速度要高於數組，因為可以依據存儲數據的部分內容找到數據在數組中的存儲位置，進而能夠快速實現數據的訪問，理想的散列訪問速度是非常迅速的。散列存儲的時間複雜度為O（1），數組為O（n）。
線性結構 VS 非線性結構
線性結構：元素之間存在一對一的關係
- 數組
- 鏈表
- 堆棧
- 隊列
非線性結構：元素之間存在一對多，多對多的關係
- 樹
- 圖
關於演算法
什麼是演算法？
來自搜狗百科：
演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規範的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間複雜度與時間複雜度來衡量。
簡單來說，演算法就是解決問題的方式，而時間複雜度和空間複雜度可以衡量演算法的性能。
【舉個栗子】
假設你要從上海到北京，那麼怎麼去就是一個待解決的問題。
提出兩種方案，乘火車，坐飛機。這兩種方式就是來解決去北京的問題的，可以理解為演算法。
但是火車和飛機是有區別的，乘火車價格更低，但耗時長，乘飛機耗時短，但價格貴。
價格和時間可以類比演算法的時間複雜度（演算法完成需要多久），空間複雜度（完成演算法需要多大記憶體空間）。
為什麼需要演算法？
演算法和設計模式類似，屬於經驗之談，是經前人們應用後總結的一種解決問題的方式。
而在經過大範圍的應用和普及之後，就會變成一種標準。
而經驗的作用就是用來學習，應用，改進的。
開源的時代，有種思想叫別造輪子。就好像愛迪生髮明了電燈，後人並不會去把發明的過程花幾十年重複一遍，而是去學習原理，在此基礎上進行改進，擴展應用，鎢絲燈到現在色彩斑斕的燈就是很好的例子。
對於演算法來說，同樣如此。如果不是專門研究演算法的工程師，對於演算法領域更多的是使用，而不是創造。
演算法的衡量標準
-
時間複雜度：演算法運行到完成需要的時間
時間複雜度是一個漸進值，
x=1;y=2; //執行兩次 for(int i =0 ;i<n ;i++) { x++; //執行n次 } for(int i =0 ;i<n ;i++) { for(int j =0;j<m;j++) { y++; // 執行n的方次 } }
程式總共執行的次數為：n2+n+2，取漸進值
時間複雜度T(n)=O(n2)
- 空間複雜度：演算法執行過程中需要的記憶體空間大小
