跳到主要內容

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

程式語言概念

資料結構與演算法

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

算法分析

目的是估計一個演算法所需要花費的時間跟空間，也是是所謂的時間複雜度(計算的次數)以及空間複雜度(所需要的記憶體)，這樣的分析無關使用的平台，只是單單跟演算法本身有關，在分析上，在意三種結果，最短時間、最長時間、平均時間，在數學表示上面，可以以下的方式來表示Ｏ(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:程式語言概念＿變數
下一單元：程式語言概念_常見的檔案類型
標籤：

留言

張貼留言

這個網誌中的熱門文章

Python-資料庫-mongodb-pymongo

Python 資料庫 mongodb-pymongo 安裝： linux、mac：pip3 install pymongo windows： import pymongo client = pymongo.MongoClient("mongodb://localhost:27017/") db = client['demo_db'] col = db['demo_col'] dict1 = { "name": "ab123ab456g", "day": "1890-04-05" } result = col.insert_one(dict1)  dict2 = [   { "name": "ki", "day": "1666-1-1"},   { "name": "aa", "day": "1222-11-11"},   { "name": "gg-gg", "day": "1333-02-22"},   { "name": "T-T", "day": "1444-03-02"},   { "name": "f-f", "day": "1555-01-01"} ] result = col.insert_many(dict2) result = col.find_one() print(result) results = col.find() for result in col.find(): print(result) results = col.find() query = {'
張貼留言
閱讀完整內容

程式語言概念-條件敘述

程式語言概念 條件敘述 上一篇的比較運算就是用來描述條件的，如變數a跟變數b，範例如下。 a>b a=>b a==b a<=b a<b a!=b 上一篇的邏輯運算可以連接不同條件，如：a>b and c>b。 在寫程式的時候，可以使用條件式加上需要的條件敘述，進行流程控制，達到程式結構化的目的，常見的條件式if-else、if-else if- else、switch。 條件式可以進行選擇流程，選擇流程種類如下。 單一選擇 雙向選擇 多向選擇 單一選擇： 用於當某些條件達成之後，就執行，如：下雨了嗎？沒有，沒事，有，帶傘。 流程圖 雙向選擇： 用於當某些條件達成之後，執行Ａ，不然執行Ｂ，如：請問數字是奇數嗎？是，奇數，不是，偶數。 流程圖 多向選擇： 用於判斷某變數是否為Ａ、Ｂ、Ｃ、...、其他，如：請問現在是什麼季節？春天、夏天、秋天、冬天。 流程圖  投影片-slideshare:程式語言概念＿變數  影片-youtube:程式語言蓋面＿變數  程式碼-Github:程式語言概念＿變數 下一單元：程式語言概念＿ 迴圈
張貼留言
閱讀完整內容

程式語言概念-資料結構

程式語言資料結構 資料結構 在討論資料結構時，必須先暸解記憶體的運作過程，首先作業系統會將記憶體(RAM)分頁，切割成特定大小的區塊，來給運作的程式使用，在程式啟動後，會先將編譯過後的程式碼載入到記憶中，並運行，而這些程式碼有些只運行一次，有些則運行多次，如程式的初始化指運行一次，如程式操作運行多次。 而在運行程式時，會運行到有變數的段落，此時就會定義一段記憶體給該變數，而其大小會隨其資料型態改變，當有相同資料型態的資料需要儲存時，通常會用陣列，把需要的資料大小告知後，把相同類型的資放在一起，而陣列是一種資料結構，其一旦宣告後，其記憶體大小就不再改變，因此有靜態的特性，所以相對的，在操作資料結構時會改變其記憶體大小的就是動態的，所以動態的資料結構，會有如何建立、如何搜尋、如何更新、如何刪除的問題，這也衍生到資料庫的CRUD(Create、Read、Update、Delete)這概念，因此在討論的時候會把時間複雜度跟空間複雜度做介紹，這樣是比較全面的做法。 而在儲存資料的時候，會有需要自訂義資料的時候，這也會影響到資料的基本大小，而自定義的型態，通常會使用struct跟class來定義，在各種語言通常struct為value type，class為refference type，兩者在意在，struct 在定義完之後可以像一般的資料型態使用，定義的變數的資料內容是存值，所以不會相互干涉，而class則會，所以class 都會使用new的宣告新的物件，不過這些東西的細部定義需要參考該官方網站的內容，此外還有point type。 常見的資料型態 陣列 array 堆疊 stack 佇列 queue 連結串列 linked list 樹 tree 圖 graph 堆 heap 雜湊表 hash 串列 list 字典 dict 其他 陣列 為靜態的，其記憶體大小在初始化之後，便不能在變動。 連結串列 為動態的資料結構的基本型，由struct、指標跟變數組成，用來構成其它的資料結構。 堆疊 與 佇 列為相似的結構，由多個連結串列組成，目的是用來儲存資料，並後存放資料先被使用，想像疊書，疊十層高，然後從上面開始拿。 佇 列 由多個連結串列組成，目的是用來儲存資料，並先存放資料先被使用，排隊的概
張貼留言
閱讀完整內容