什么是算法

算法是完成一组任务的指令。 例如:如何大便 脱裤子,拉屎,冲马桶 或者脱裤子,拿本书,看书,拉屎,冲马桶 或者冲马桶,拉屎,脱裤子 或者脱了裤子,去冰箱拿块榴莲,将榴莲放到微波炉,穿上裤子,深呼吸 这些过程,对于你要完成大便,都是算法

什么是算法性能

哪个过程拉的效率更高,就是你拉屎算法的性能 也有不同的角度,看待性能,拉的快,拉的舒服,拉的有品味

在编程领域就是时间的复杂度与空间的复杂度 也就是说,哪个计算次数少,哪个占用资源少

代数知识

f(x) = x * 2 f(5)的值是多少,如果你说是10,那么恭喜你,接下来的内容你都能看懂

二分查找

假设一本写真集,有100页,你喜欢的三上悠亚的果照在37页。 你会怎么翻找? 从第一页开始一页一页开始找。。。 耐心非常好,这样的方式叫做简单查找,简称傻找 或者是翻到中间,如果页数比37大就向前翻,如果你这么做过,恭喜你,你应用过二分查找

对数

你可能忘记了什么是对数,但是可能记得什么是幂。 $\log _10$100 相当于问“将多少个10相乘等于100”。答案是2个:10 * 10 = 100 因此$\log _10$100 = 2。 对数运算是幂运算的逆运算。

$10 ^2$=100 $log _10$100=2 $10 ^3$=1000 $log _10$1000=3 $2 ^3$=8 $log _2$8=8 $2 ^4$=16 $log _2$16=4 $2 ^5$=32 $log _2$32=5

假设有1,2,3,4,5,6。。。100 100个数要猜 使用二分查找也就是求$log _2$100=7

譬如要猜1,2,3,4,5,6,7,8 第一次猜是4 如果数字是5,那么剩余要猜的数是:5,6,7,8 一共剩余四个数字 即 $\log _2$8=3 $2 ^3$=8
再猜是6 $\log _2$4=2 $2 ^2$=4
再猜1次即可确定是5 $\log _2$2=1 $2 ^1$=2

所以$\log _2$8 =3 三次即是8个数字的二分查找的复杂度

前提

二分查找的前提是列表必须有序的。

代码实现

可以设想两个指向数组头尾的变量

mid = (low + high)/2
guess = list[mid]

只要 low<=high 就循环比较guess与要猜的值 if guess == item { return mid } if guess > item { high = mid - 1 } else { low = mid + 1 }

运行时间

简单查找 二分查找
100个元素 最多需要猜100次 100个元素最多需要猜7次
4000 000 000个元素 最多需要猜 4000 000 000次 4000 000 000个元素 最多需要猜32次
O(n) O($\log _n$)

大O表示法

大O表示法,让你能够比较操作次数,它指出了算法运行时间的增速。

常见的大O运行时间 O(log n) 对数时间 O(n) 线性时间 O(n * log n) 快排 O($n ^2$) 选择排序 O(n!) 旅行商问题非常慢

小结

  • 二分查找的速度比简单查找快的多
  • O(log n)比O(n)快。元素越多越快
  • 算法运行时间不以秒为单位
  • 算法的运行时间是从其增速的角度度量的
  • 算法运行时间用大O表示法表示