跳到主要內容

程式語言概念-演算法

程式語言概念
演算法

演算法基本上，分成排序、搜尋、最短路徑單源、最短路徑多源、最小生成樹、最大流量最小割、拓樸排序、線性規劃、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-開啟檔案

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