算法列表

算法列表

算法列表,為各類算法的集合。計算機歸納為的五大常用算法,它們是貪婪算法,動態規划算法,分治算法,回溯算法以及分支限界算法。五個算法是有很多套用場景的,最最佳化問題大多可以利用這些算法解決。算法的本質就是解決問題。

基本介紹

  • 中文名:算法列表
  • 外文名: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)

相關詞條

熱門詞條

聯絡我們