2.4 算法入门（Intro to Algorithms）

2.4.1 概述

算法

算法（Algorithm）一词源自 1000 多年前的波斯博识者，阿尔·花拉子密(Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī), 代数（algebra）之父之一。

算法是指求解问题的具体步骤，一般来说所需步骤越短越好，但有时也会考虑占用内存的情况。

复杂度

算法的输入大小和运行步骤之间的关系叫做「算法复杂度」，使用「大 O 表示法」来衡量运行速度的量级。

2.4.2 选择排序（Selection sort）

遍历找到当前最小数，移动至最前，后从第二个继续循环该遍历，直到最后一个数字。算法时间复杂度为 $O（N^2）$，指数级增长，效率较低。

2.4.3 归并排序（merge sort）

若数组大小大于 1，则将数组对半分割，直至单个数组个数为 1（示例中）。接着从首个开始两两对比每组中第一个数字的大小，归并为 * 2 个组，循环重复。

算法时间复杂度为 $O（nlogn）$ ，n 为比较 + 合并的次数（与输入成正比），log n 是合并步骤的次数（重复对半切是和输入呈对数关系）。

2.4.4 Dijkstra 算法

Dijkstra 是一种图搜索（graph search）算法，图由节点（node）和边（line）相连构成，点到点之间的代价称为成本（cost）或是权重（weight）。

若要计算任意某两点之间的最小代价路线，最简单的蛮力法是尝试每一条路计算总成本，时间复杂度为 $O(n!)$，阶乘量级是最糟糕的。

Dijkstra 算法是 Edsger Dijkstra 发明与 1956 年构思的算法，其基本思想如下：总是从代价最低的节点开始，运行一次后得知相邻节点的代价；再从相邻节点中的最小节点开始向前计算相邻节点的邻居的代价，更新该值，接着计算相邻节点中的第二小节点向前一步的代价，若相邻节点的同一邻居计算结果再次计算时比原值更小，则更新。

1956 年初始版本的 Dijkstra 算法的时间复杂度是 $O(n)$，经改进后为 $O(nlog+l)$，其中 n 为节点数，l 为边数。