点击查看【bilibili】

  • 算法：解决问题的具体步骤
  • 复杂度：评价算法的优劣
    • 时间复杂度：算法的步骤多少（耗时）
    • 空间复杂度：算法占用内存多少
  • 大 O 表示法 —— 表示算法复杂度
    • O(N)

排序算法

选择排序 Selection sort

定义：首先在未排序序列中找到最小（大）元素，与序列起始位置元素交换位置，存放到排序序列的起始位置；然后，再从剩余未排序元素中继续寻找最小（大）元素，交换放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
特征：选择排序是不稳定的排序方法。
时间复杂度：O(N2)
image.png
伪代码如下：

  1. def selectionSort(array):
  2.     for i in range(0, len(array) - 1):
  3.         smallest = i    # 最小数的下标
  4.         for index in range(i + 1, len(array)):
  5.             if array[index] < array[smallest]:
  6.                 smallest = index
  8.         swap(array[i], array[smallest])
  10.     return array

归并排序 Merge sort

定义：若排序数组长度大于1，则将待排序数组分成两半，再分成两半，再分，直到分成的数组长度为1。再两两合并，合并过程中，两个值按序排列，即合并成有序序列；再继续将有序的子序列两两排序+合并，再排序+合并，直到合并成一个总体的有序序列。
特征：归并排序是稳定排序算法
复杂度：O(N*logN)
image.png

图搜索 graph search

“图” 是用线连起来的一堆 “节点”。如下图所示，可以想象成一个地图，每个节点代表一个城市，每条线代表一条公路，线上的数字代表 成本(cost) 或 权重(weight) ，在这里指通过该公路需要花费的时间。图搜索就是要找到一条从 高庭 到 凛冬城 用时最短的路径。
image.png
如果使用暴力算法，尝试每一种路径组合，则时间复杂度高达 O(N!)

Dijkstra 算法

定义：从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
时间复杂度：O(N2) 。这个效率不够好，意味着输入不能很大，比如不能输入一个国家的完整线路图。幸运的是，Dijkstra 算法几年后得到改进，时间复杂度优化为 O(N log N + L)，N 是节点数，L是线数。
image.png