程式語言概念-資料結構與演算法

程式語言概念

資料結構與演算法

有人認為程式=資料結構+演算法，從這邊就可以知道資料結構跟演算法的重要性，資料結構會去討論資料在記憶體中是如何存放的，用怎樣的方式存放，演算法會去討論這些資料如何分析、使用。

算法分析

目的是估計一個演算法所需要花費的時間跟空間，也是是所謂的時間複雜度(計算的次數)以及空間複雜度(所需要的記憶體)，這樣的分析無關使用的平台，只是單單跟演算法本身有關，在分析上，在意三種結果，最短時間、最長時間、平均時間，在數學表示上面，可以以下的方式來表示Ｏ(big-omicron)、 Ω（big-omega）、Θ（big-theta）、ο（little-omicron）與 ω（little-omega），常用的為big-omicrm，其意義為上限的概念。

• f(n) ∈ Ο(g(n)) ≈ a ≤ b
• f(n) ∈ Ω(g(n)) ≈ a ≥ b
• f(n) ∈ Θ(g(n)) ≈ a = b
• f(n) ∈ ο(g(n)) ≈ a < b
• f(n) ∈ ω(g(n)) ≈ a > b

以下是常見函數的時間複雜度，所以在演算法選擇上，常數優先，再來是log2N。

以下是演算法分析範例，

資料結構

資料結構跟資料用何種方式存放在記憶體有關，從先前的資料型態可以知道不同的形態可以需要的記憶體大小會不一樣，而類別或結構會把這些定義好的新類型放在記憶體上的同一個區塊，再來相關屬性或是相同屬性的資料該如何存放在記憶體當中呢？如果我的資料的量會隨時間變化呢？如果我的每筆資料跟每筆資料之間存在某種關係呢？

從記憶體可不可以變動這件事情，可以分成動態的資料結構跟靜態的資料結構，如下：

• 靜態資料結構：陣列
• 動態資料結構：用指標串接起來的資料結構

陣列

簡單說就是把一堆一樣的資料放在一起，可以放程式語言本來就有的資料型態，如：整數，或是可以放自定義的資料型態，如用類別或結構定義的，也因為是靜態的所以必須先定義出陣列大小。

用指標串接起來的資料結構

如串列、堆疊、佇列、樹、圖、hash table，前三個比較跟處理資訊有關，後面四個比較跟存放資料或是資料存在某種特定關係。
在看資料結構的時候，需要了解各種操作的成本，常見的操作有建立、新增、更新、刪除、搜尋、排序、清空。

演算法

排序、搜尋、最短路徑單源、最短路徑多源、最小生成樹、最大流量最小割、拓樸排序、線性規劃、hash function、近似、隨機、分制法、動態編程、貪婪、其他，以上都是常見的演算法，，演算法的目的在有效率的處理所遇到的問題，而問題得種類會在之後的文章針會上述的演算法一一分析、解釋。

---

 投影片-slideshare:程式語言概念＿變數

 影片-youtube:程式語言蓋面＿變數

 程式碼-Github:程式語言概念＿變數
下一單元：程式語言概念_常見的檔案類型