跳到主要內容

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

程式語言概念

資料結構與演算法

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

算法分析

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

Python-開啟檔案

Python 開啟檔案 基本概念說明 參考 程式語言概念-常見檔案型態 基本常見檔案類型 二進位檔 文字檔 CSV XML JSON html excel word 圖片 音源 影片 以下是處理該類型檔案對應函式或模組 這邊內建函數的意思是讀取之後能直接處理。 檔案類型 內建函數 標準模組 非標準模組 二進位檔 open() None - 文字檔 open() None - CSV None csv - XML None xml - JSON None json - html None html - excel None None 非 windows excel api windows excel api word None None 非 windows word api windows word api 圖片 None None pypng 音源 None wave - 影片 None None moviepy 二進位檔程式碼範例 二位元的定義在Python官網的資料型態沒有定義，但是還是可以使用的需要用函式轉換才能夠出現，分別用bytes、bytearray兩種，在使用前可以先盡到直譯器上，用help指令查訊該function的功能，以下是其內容。 在前面先講bytes跟bytearray用法，後續再講數字、字串轉成bytes的方法，最後才是進行二進位檔案讀寫。 bytes 再把資料料轉換時輸入內容可分成一下種類 整數 字串 可迭代資料：迭代內容一定要是數字 buffer：這邊不是示範，因為寫python沒用過 bytes(1) bytes(2) bytes(3) bytes(4) bytes('str'.encode('utf8')) bytes('str'.encode('ascii')) bytes([0,1,255]) bytes((2)) bytes((1,2)) bytes({1,2}) 程式碼說明 bytes()中代入數字是告知bytes數量，如：bytes(1)就是一個bytes量 bytes()中代入字串時，附加編
張貼留言
閱讀完整內容