算法图解
======================================
算法简介
二分查找
二分查找能解决什么问题?
在有序的元素列表中快速的找到指定元素位置。使用二分查找可以将查找步骤减少到 $log_2n$ 步
二分查找的原理
通过猜测中间的数字,从而每次都将余下的数字排除一半,从而减少查找的次数
对应JS代码
1 | var binary_search = function(list, item){ |
练习
- 假设一个包含128个名字的有序列表,你要是用二分查找在其中查找一个名字,请问最多需要几步才能找到 (7步)
- 上面列表的长度翻倍后,最多需要几步? (8步)
大O表示法
大O表示法是一种特殊的表示法,指出了算法的速度有多快。大O表示法指出了算法有多快,需要执行的操作数。
一些常见的大O运行时间
- $O(log,n)$,也叫对数时间,这样的算法包括二分查找。
- $O(n)$,也叫线性时间,这样的算法包括简单查找。
- $O(n * log n)$,这样的算法包括快速排序。 一种速度较快的排序方法
- $O(n^2 )$,这样的算法包括选择排序。 一种速度较慢的排序方法
- $O(n!)$,这样的算法包括接下来将介绍的旅行商问题的解决方案。 一种非常慢的算法
使用这几种算法绘制一个16格的网格需要的时间如下:
小结
- 二分查找的速度比简单查找快的多。
- $O(log,n)$比$O(n)$快。需要搜索的元素越多,前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
- 算法运行时间用大O表示法表示
选择排序
数组与链表的区别
链表
- 链表中的元素可以存储再内存的任何地方
- 链表的每个元素都存储了下一个元素的地址
- 链表的优势在于插入元素方面。
- 链表的读取速度很慢
- 链表更适合中间插入数据(只需要修改他前面的元素指向的地址)
- 链表更适合删除元素
数组
- 数组中的内存必须是相连的。
- 数组的效率很高。
- 数组对内存的使用效率较低
选择排序
将混乱的排序,按照一定的顺序进行排序,排序所需要的总时间为 $O(n^2)$。
选择排序应用
- 电话簿中的人名
- 旅行日期
- 电子邮件
选择排序的优缺点
虽然选择排序是一个灵巧的算法,但其速度不是很快,下章的快速排序速度更快,请运行时间为 $O(n,log,n)$。
对应JS代码
1 | var findSmallest = function(arr){ |
小结
- 计算机内存犹如一大堆抽屉
- 需要存储多个元素时,可以使用数组或链表
- 数组的元素都在一起
- 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快
- 链表的插入和删除速度很快
- 在同一个数组中,所有元素的类型必须相同
递归
如何选择
如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。
基线条件和递归条件
每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。
对应js代码
1 | var fact = function(x){ |
小结
- 递归指的是调用自己的函数
- 每个递归函数都有两个条件:基线条件和递归条件
- 栈有两种操作:压入和弹出。
- 所有函数调用都进入调用栈。
- 调用栈可能很长,这将占用大量的内存。
快速排序
分而治之(divided and conquer,D&C)
① 找出基线条件,尽可能的简单
② 不断讲问题分界,或者说缩小规模,使其满足基线条件
使用循环完成数组内数字相加js代码
1 | var arr = [2,4,6]; |
使用递归JS代码
1 | var arr = [2,4,6]; |
练习3 找出数组中最大的数字
1 | var arr = [1,3,5,7,9,11,13,15,17,19]; |