-
算法列表
鎖定
- 中文名
- 算法列表
- 外文名
- List of Algorithm
- 領 域
- 計算機科學
- 含 義
- 各類算法的集合
- 舉 例
- 排序算法列表
- 包 含
- 算法
算法列表數據結構
算法列表鏈表
- 鏈表是一種由節點(Node)組成的線性數據集合,每個節點通過指針指向下一個節點。它是一種由節點組成,並能用於表示序列的數據結構。
- 單鏈表:每個節點僅指向下一個節點,最後一個節點指向空(null)。
- 雙鏈表:每個節點有兩個指針p,n。p指向前一個節點,n指向下一個節點;最後一個節點指向空。
- 時間複雜度:
- 索引:O(n)
- 查找:O(n)
- 插入:O(1)
- 刪除:O(1)
算法列表棧
- 棧是一個元素集合,支持兩個基本操作:push用於將元素壓入棧,pop用於刪除棧頂元素。
- 時間複雜度
- 索引: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)
- 參考資料
-
- 1. 李靜梅, 王雪, 吳豔霞. 一種改進的優先級列表任務調度算法[J]. 計算機科學, 2014, 41(5):20-23.
- 2. 技術面試寶典: 很全面的算法和數據結構知識 .伯樂在線[引用日期2017-06-13]