场景
电话本
- 假设从电话本里面找 youjie 的电话，最常见的不是从开头开始找，而是从中间开始查找
- 电话本是有序列表
1-100 猜想
想起来小时候看过诸葛亮的一个虚构小故事。一次诸葛亮在军营里被军士质疑是不是真的很聪明。诸葛亮说你在1-1000里随便想个数字说出来，我能在10次以内猜到它。那么怎样以目标最少的次数猜到这个数字？
简单查找
- 如果从 1 开始猜，这叫简单查找，换句话说就是傻找
- 如果是 99，那么得猜 99 次（临界点就是这个数）
二分查找
- 如果从中间值开始猜
- 那么临界点就是 99，最坏的情况下只用猜七次，50 错，75 错..这样猜
那么得出结论，对于 n 个元素，用二分查找最多需要 log2（n） 步，简单查找最多需要 n 步
2^log2 （n）=n，log 叫对数运算，2^n 叫幂运算，他们互为逆运算
算法实现
注意二分查找法必须是有序的，简单来说就是分一半
大 O 表示法
指出的是最糟情况下的运行时间，也可以说是操作数
- 这里用大 O 表示法讨论运行时间，都是讨论的最糟糕的临界值，比如简单查找 100 个元素，就是要看每一个元素。二分查找也是查看最远的，那么就只用查看 log100 个元素约为 7
- log 时间这里的底数默认是 2，也就是默认是 log2
- 其实我们是用幂运算的眼光来看，我们求的运行时其实就是指数
概念
- 大 O 表示法指出了算法有多快。例如，假设列表包含 n 个元素，简单查找需要检查每个元素，因此需要执行 n 次查找,运行时间位 O（n）
- O(n),单位不是秒，大 O 表示法指的并不是以秒为单位的速度，而是能够比较操作数，它指出了算法运行时间的增速
- 所以 n 是操作数的意思
- 谈论算法的速度，是随着输入的增加，其运行事件将以怎么样的速度增加
常见的大 O 运行时间
由快到慢的经常遇到的五种，可以自己想象一下坐标系图
- O（log n）,也叫对数时间，这样的算法包括二分查找
- O(n)，线性时间，包括简单查找
- O(n*log n)，包括快速排序（业界俗称快排），一种速度较快的快速排序
- O（n^ 2）,包括选择排序，一种速度较慢的排序算法
- O（n！），包括旅行商问题的解决方案，一种非常慢的算法
旅行商问题
旅行商要前往 5 个城市，同时确保旅程最短，这样它要每个城市都去，然后计算总旅程，再挑选路线最短的
- 5 个城市有 120 种不同的排列方式，因此需要 120 次操作
- 这是一个非常非常慢的算法，但是这个问题也是计算机科学领域待解决的问题
