跳到主要內容

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

程式語言概念

資料結構與演算法

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

算法分析

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

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()中代入字串時，附加編...
張貼留言
閱讀完整內容

Python-設計模式-共享模式

Python 設計模式 共享模式 class Font:     def __init__(self):        self.Size = 0        self.Type = ''     def printAll(self):        print(self.Size, self.Type)  class FontFacotry:     def Word(self, Size=3, Type='1'):        F = Font()        F.Size = Size        F.Type = Type        return F  FontSize = [1,2,3] FontType = ['1','2','3'] Facotry = FontFacotry()  F1 = Facotry.Word(FontSize[0],FontType[0])  F1.printAll()  F2 = Facotry.Word( FontSize[1],FontType[1] ) F2.printAll()  F3 = Facotry.Word( FontSize[2],FontType[2] ) F3.printAll() 程式碼說明 font 定義類別 fontFacotry物件生成工廠 fontsize用來儲存font大小的外部空間 fonttype用來儲存font種類的外部空間
張貼留言
閱讀完整內容

語言學習-English-The Scientist

Song Lyric Title :  The Scientist Singer :Coldplay Album :A Rush of blood to the head Release Date :  2002 Come up to meet you Tell you I'm sorry You don't know how lovely you are I had to find you Tell you I need you Tell you I set you apart Tell me your secrets And ask me your questions Oh let's go back to the start Running in circles, coming up tails Heads on a science apart Nobody said it was easy It's such a shame for us to part Nobody said it was easy No one ever said it would be this hard Oh take me back to the start I was just guessing at numbers and figures Pulling your puzzles apart Questions of science, science and progress Do not speak as loud as my heart Tell me you love me Come back and haunt me Oh and I rush to the start Running in circles, chasing our tails Coming back as we are Nobody said it was easy Oh it's such a shame for us to part Nobody said it was easy No one...
張貼留言
閱讀完整內容