跳到主要內容

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

程式語言概念

資料結構與演算法

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

算法分析

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

class Objects, values and types CPython implementation detail:  For CPython,  The standard type hierarchy User-defined functions __doc__ The function’s documentation string, or  None  if unavailable; not inherited by subclasses Writable __name__ The function’s name Writable __qualname__ The function’s  qualified name New in version 3.3. Writable __module__ The name of the module the function was defined in, or  None  if unavailable. Writable __defaults__ A tuple containing default argument values for those arguments that have defaults, or  None  if no arguments have a default value Writable __code__ The code object representing the compiled function body. Writable __globals__ A reference to the dictionary that holds the function’s global variables — the global namespace of the module in which the function was defined. Read-only __dict__ The namespace supporting arbitrary function attributes. Writable __closure__ None ...
張貼留言
閱讀完整內容

Python-開啟檔案-excel

Python 開啟檔案 excel 安裝: linux、mac :pip3 install openpyxl、pip3 install xlwt、pip3 install xlrd windows    :之後補上 程式碼說明 2007年版後 寫入 from openpyxl import Workbook,load_workbook wb = Workbook() ws = wb.active ws1 = wb.create_sheet('Mysheet') ws2 = wb.create_sheet('Mysheet', 0) ws1.title = 'New Title' print(wb.sheetnames) ws['A4'] = 4 ws.cell(row=4, column=2, value=10) wb.save('demo.xlsx')  讀取 wb_load = load_workbook('demo.xlsx')  sheet_ranges = wb_load['Sheet'] print(sheet_ranges['A4'].value) 2007年版前 寫入 import xlwt from datetime import datetime style0 = xlwt.easyxf('font: name Times New Roman, \ color-index red, bold on',num_format_str='#,##0.00') style1 = xlwt.easyxf(num_format_str='D-MMM-YY') wb = xlwt.Workbook() ws = wb.add_sheet('A Test Sheet') ws.write(0, 0, 124, style0) ws.write(1, 0, datetime.now(), sty...
張貼留言
閱讀完整內容

python-設計模式-迭代器模式

python 設計模式 迭代器模式 class Item:    def __init__(self, name, price):       self.name = name        self.price = price     def __str__(self):        return "{}: $ {}".format(self.name, self.price)  class MenuIterator:     def __init__(self, items):        self.indx = 0        self.items = items     def has_next(self):        return False if self.indx >= len(self.items) else True      def next(self):        item = self.items[self.indx] self.indx += 1 return item      def remove(self):        return self.items.pop()  class Menu:      def __init__(self):         self.items = []      def add(self, item):         self.items.app...
張貼留言
閱讀完整內容