二分查找和大O表示法

• 如果从中间值开始猜
• 那么临界点就是 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 次操作
• 这是一个非常非常慢的算法，但是这个问题也是计算机科学领域待解决的问题