引言

本文集是作者阅读《算法图解》一书所做的读书笔记，内容难免过于浅薄。之后将针对部分细节进行补充和完善，如有错漏还望读者留言指正。

算法是一组完成任务的指令，任何代码片段都可视为算法。优秀的算法可以提高程序执行效率，或者解决一些有趣的问题。在学习算法的过程中我们可以尝试理解算法的思路和应用场景，从而开阔视野，提升自身水准。

大O表示法
大O表示法是一种特殊的表示法，用来表示算法处理数据花费的时间随数据规模变化的规律，即算法的时间复杂度。
下面以简单查找算法为例进一步了解算法复杂度的概念以及大O表示法的使用方法。

public int search(int key, int[] arr) {
  for (int idx = 0; idx < arr.length; idx++) {
    if (key == arr[idx]) {
      return idx;
    }
  }
  return -1;
}

以上代码实现了一个简单的查找算法，search()方法接收两个参数，key为要查找的目标，arr为查找的集合，如果arr中包含该元素则返回元素的下标，否则返回-1。
假设检查一个元素花费的时间为1，上面的算法当中在最差的情况下需要检查的次数为arr.length，平均检查次数为1/2 * arr.length，所以上面查找算法查找元素花费的时间可以表示为t = 1/2 * arr.length。使用大O表示法时通常会省略表达式中的常数项，所以简单查找算法的时间复杂度为O(n)。
了解算法复杂度的意义在于：通过算法时间复杂度可以比较不同算法的操作数，计算算法运行时间随数据规模的增速，从而评价算法的质量。

常见的大O运行时间有以下几种：

1. O(logN), 也叫对数时间。
2. O(N), 也叫线性时间。
3. O(N*logN)。
4. O(N²)。
5. O(N!)。

下图来自Time complexity - Wikipedia，图中展示了常见算法复杂度的操作数随输入规模变化的曲线。

Comparison computational complexity

至此引言部分结束，后续内容将涉及常见排序算法，查找算法以及简单的图算法。

---

作者水平有限，本文旨在记录作者阅读和学习过程，内容质量难以保证，暂不支持转载，还望见谅