算法列表,為各類算法的集合。計算機歸納為的五大常用算法,它們是貪婪算法,動態規划算法,分治算法,回溯算法以及分支限界算法。五個算法是有很多套用場景的,最最佳化問題大多可以利用這些算法解決。算法的本質就是解決問題。
基本介紹
- 中文名:算法列表
- 外文名:List of Algorithm
- 領域:計算機科學
- 含義:各類算法的集合
- 舉例:排序算法列表
- 包含:算法
數據結構
鍊表
- 鍊表是一種由節點(Node)組成的線性數據集合,每個節點通過指針指向下一個節點。它是一種由節點組成,並能用於表示序列的數據結構。
- 單鍊表:每個節點僅指向下一個節點,最後一個節點指向空(null)。
- 雙鍊表:每個節點有兩個指針p,n。p指向前一個節點,n指向下一個節點;最後一個節點指向空。
- 循環鍊表:每個節點指向下一個節點,最後一個節點指向第一個節點。
- 時間複雜度:
- 索引:O(n)
- 查找:O(n)
- 插入:O(1)
- 刪除:O(1)
棧
- 棧是一個元素集合,支持兩個基本操作:push用於將元素壓入棧,pop用於刪除棧頂元素。
- 後進先出的數據結構(Last In First Out, LIFO)
- 時間複雜度
- 索引:O(n)
- 查找:O(n)
- 插入:O(1)
- 刪除:O(1)
佇列
- 佇列是一個元素集合,支持兩種基本操作:enqueue 用於添加一個元素到佇列,dequeue 用於刪除佇列中的一個元素。
- 先進先出的數據結構(First In First Out, FIFO)。
- 時間複雜度
- 索引:O(n)
- 查找:O(n)
- 插入:O(1)
- 刪除:O(1)
樹
- 樹是無向、聯通的無環圖。
二叉樹
- 二叉樹是一個樹形數據結構,每個節點最多可以有兩個子節點,稱為左子節點和右子節點。
- 滿二叉樹(Full Tree):二叉樹中的每個節點有 0 或者 2 個子節點。
- 完美二叉樹(Perfect Binary):二叉樹中的每個節點有兩個子節點,並且所有的葉子節點的深度是一樣的。
- 完全二叉樹:二叉樹中除最後一層外其他各層的節點數均達到最大值,最後一層的節點都連續集中在最左邊。
二叉查找樹
- 二叉查找樹(BST)是一種二叉樹。其任何節點的值都大於等於左子樹中的值,小於等於右子樹中的值。
- 時間複雜度
- 索引:O(log(n))
- 查找:O(log(n))
- 插入:O(log(n))
- 刪除:O(log(n))
字典樹
- 字典樹,又稱為基數樹或前綴樹,是一種用於存儲鍵值為字元串的動態集合或關聯數組的查找樹。樹中的節點並不直接存儲關聯鍵值,而是該節點在樹中的位置決定了其關聯鍵值。一個節點的所有子節點都有相同的前綴,根節點則是空字元串。
排序算法
快速排序
- 穩定:否
- 時間複雜度
- 最優:O(nlog(n))
- 最差:O(n^2)
- 平均:O(nlog(n))
合併排序
- 合併排序是一種分治算法。這個算法不斷地將一個數組分為兩部分,分別對左子數組和右子數組排序,然後將兩個數組合併為新的有序數組。
- 穩定:是
- 時間複雜度:
- 最優:O(nlog(n))
- 最差:O(nlog(n))
- 平均:O(nlog(n))
桶排序
- 桶排序是一種將元素分到一定數量的桶中的排序算法。每個桶內部採用其他算法排序,或遞歸調用桶排序。
- 時間複雜度
- 最優:Ω(n + k)
- 最差: O(n^2)
- 平均:Θ(n + k)
基數排序
- 基數排序類似於桶排序,將元素分發到一定數目的桶中。不同的是,基數排序在分割元素之後沒有讓每個桶單獨進行排序,而是直接做了合併操作。
- 時間複雜度
- 最優:Ω(nk)
- 最差: O(nk)
- 平均:Θ(nk)