跳到主要內容

程式語言概念-演算法

程式語言概念
演算法

演算法基本上，分成排序、搜尋、最短路徑單源、最短路徑多源、最小生成樹、最大流量最小割、拓樸排序、線性規劃、hash function、近似、隨機、分制法、動態編程、貪婪等議題的討論，在進行程式優化時，會對函式庫所使用到的演算法，重新撰寫，以節省編譯跟載入時間。
以下就依序對上述議題進行討論，另外比較的時候，需要用同樣的資料結構進行比較。

交換(Swap)

最基本的概念，用於把兩筆資料的記憶體位置互換，所有演算法都會用到。

排序

排序主要目的是對資料進行值得比較，並依照大小順序排序，由小開始，亦可由大開始。
以下是排序演算法種類，氣泡、選擇、插入、快速、合併、堆疊、桶

氣泡：最簡單的排序演算法，把數值大的往後移動或是把數值小的往前移動，另有同時進行兩種動作的shaker sort。

選擇：找尋最小值或最大值，並將移動到最前位置之後，依序知道所有元素執行完成。

插入：把資料分成已完成排序的區域以及未完成的區域，並把未完成區域的資料不停放入已完成的區域。

快速*：選定一直當作基準值，與基準值比較交換資料位置，再將基準值兩側的值進行前述排序，直到排序結束。

合併*：分制法應用，把資料拆成小資料在合併。
堆疊*(二元堆疊)：以樹的結構進行排序，把樹中最大的值移動在上放位置，之後數字再依序排序，此演算法是利用樹的搜尋速度的優勢。

桶*：把資料分到個別的桶中進行排序，然後再合併。
常用的排序法有，快速、合併、堆疊、桶，快速為大多語言預設的演算法，合併需要額外的記憶體，堆疊目前應用來進行排序執行順序，桶在資料龐大時可以拆散資料進行排序。
各種排序時間複雜度比較

搜尋

搜尋主要目的是為了對已經建立的資料結構，對其內容進行搜尋，搜尋特定的資料，所以針對不同的資料結構會有不同的演算法，常見的有Linear Search、binary tree Search、深度優先搜尋、廣度優先搜尋、A*

Linear Search：一一比對進行搜尋

binary tree Search：把資料轉成binary tree(有排序過的)後，再進行搜尋，缺點需要花費時間轉乘binary tree。

深度優先搜尋：對樹或圖進行搜尋，在搜尋時會以深度作為優先，會往下走直到無法往下走為止

廣度優先搜尋：對樹或圖進行搜尋，在搜尋時會以寬度作為優先，會往旁枝走直到沒有旁枝為止

A*:主要用於圖的資料結構，用來搜尋兩點之間的路徑。

最短路徑單源


主要用來解決兩點最短路徑問題，常見的有Dijkstra's algorithm(不可以有負權重)、Bellman–Ford algorithm(可以有負環)、Floyd-Warshall algorithm(可以有負權重，但不可以有負環)。

最短路徑多源

同最短路徑單源，並重複對各源進行運算。

最小生成樹

找尋圖中，連接所有點的最小權重生成，並把結果存成樹，也就是把圖轉成樹，此樹的權重是此圖的最小權重，常見的有Prime、Krustal。

最大流量最小割

最大流量就等於割最小流量，也就是把圖分成兩邊，而把圖型分成兩邊的那條線，就是所謂的割，而最大流量必定不能超過此割，此割的流量必須最小，有最大流量最小割定理對此進行證明，常見演算法有ford-fulkerson、edmonds-karp，用於網絡需要最大流量，如管路、網路或財務決策。

拓樸排序

DAG圖才能進行拓樸排序，可以把流程中的活動進行排序，決定順序。

線性規劃

線性規劃是在優化問題中的重要地位，在作業研究中遇到的問題，都可以處理。

hash function

MD5、SHA1用於加密、壓縮、解壓縮的演算法。

近似

最部分進行最佳化，常用的有線性規劃、貪婪演算法。

隨機

在演算法中加入隨機函數。

分治法

分治法是將問題拆成小問題、運算、再合併，但是這些小問題彼此之間無關連性。

動態規劃

動態規劃是將問題用數學模型描述，並拆成小問題、運算、再合併，但是這些小問題彼此之間有關連性。

貪婪

貪婪是將問題拆成小問題、運算、再合併，但是運算是對小問題最佳化。
練習-高中生解題系統-https://cat.nknush.kh.edu.tw/
標籤：

留言

張貼留言

這個網誌中的熱門文章

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...
張貼留言
閱讀完整內容