跳到主要內容

程式語言概念-演算法

程式語言概念
演算法

演算法基本上，分成排序、搜尋、最短路徑單源、最短路徑多源、最小生成樹、最大流量最小割、拓樸排序、線性規劃、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-資料庫-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 = {'...
張貼留言
閱讀完整內容

語言學習-English-Lights

Song Lyric Title : Lights Singer :Ellie Goulding Album :  Bright Lights Release Date :  2011 I had a way then losing it all on my own I had a heart then but the queen has been overthrown And I'm not sleeping now the dark is too hard to beat And I'm not keeping up the strength I need to push me You show the lights that stop me turn to stone You shine it when I'm alone And so I tell myself that I'll be strong And dreaming when they're gone 'Cause they're calling, calling, calling me home Calling, calling, calling home You show the lights that stop me turn to stone You shine them when I'm alone Noises, I play within my head Touch my own skin and hope they'll still be there And I think back to when my brother and my sister slept In and on my place the only time I feel safe You show the lights that stop me turn to stone You shine it when I'm alone And so I tell myself that I'...
張貼留言
閱讀完整內容

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