==========
== Soda ==
==========

300分钟搞定算法

算法

高级数据结构

优先队列的本质是一个二叉堆结构。堆在英文里叫 Binary Heap,它是利用一个数组结构来实现的完全二叉树。换句话说,优先队列的本质是一个数组,数组里的每个元素既有可能是其他元素的父节点,也有可能是其他元素的子节点,而且,每个父节点只能有两个子节点,很像一棵二叉树的结构。

牢记下面优先队列有三个重要的性质。

  1. 数组里的第一个元素 array[0] 拥有最高的优先级别。
  2. 给定一个下标 i,那么对于元素 array[i] 而言:
    • 它的父节点所对应的元素下标是 (i-1)/2
    • 它的左孩子所对应的元素下标是 2×i + 1
    • 它的右孩子所对应的元素下标是 2×i + 2
  3. 数组里每个元素的优先级别都要高于它两个孩子的优先级别。

优先队列最基本的操作有两个。

  1. 向上筛选(sift up / bubble up)
    时间复杂度:O(logk)
  2. 向下筛选(sift down / bubble down)
    时间复杂度:O(logk)

初始化一个大小为 n 的堆,所需要的时间是 O(n)

排序

基本&常考

  • 冒泡排序(Bubble Sort) O(n²) o
  • 插入排序(Insertion Sort) O(n²) o
  • 归并排序(Merge Sort) O(nlogn)/O(n) o
  • 快速排序(Quick Sort) O(nlogn)-O(n²)/O(logn) o
  • 拓扑排序(Topological Sort)
    其他排序算法
  • 堆排序(Heap Sort)
  • 桶排序(Bucket Sort)

递归与回溯

递归

  • 汉诺塔
    时间复杂度:
  • 迭代法 !
  • 公式法 !