什么是算法？
算法的定义是完成一项任务的一系列步骤，就像一份食谱，第一步干什么，第二步干什么... 在计算机科学中，算法是完成一个任务的一系列步骤，对于完成一个任务，有好的算法也有坏的算法，找到一个优秀的算法可以让任务高效的完成。一个好的算法要满足两点正确性和高效，但是有时候也不要去完全正确足够好就行，比如一项任务要得到一个完全正确结果需要非常长的时间。
找到立方根
给一个数怎么找到它的立方根呢？我们知道无法找到随便一个数的精确立方根，所以我们可以接受一定误差。
我们可以让从0开始不断的增加它的大小，看它的三次方有多接近
，找出最接近
的数。
def cuberoot(n):
inc = 0.001 # 每次递增的数，越小精度越大
eps = 0.01 # 可接受的误差范围
ans = 0.0
while abs(ans ** 3 - n) >= eps and ans < abs(n):
ans += inc
if n < 0: ans *= -1
return ans
可以猜到当很大时，这个算法需要的时间就非常长。那么有什么更好的算法？
二分搜索算法
二分搜索算法（binary search）也叫折半搜索，是一种在有序数组中查找某一特定元素的搜索算法。从数组的中间开始寻找，看是不是要找的数，如果不是就看这个数字是大于还是小于要找的数，然后把不对的那一半扔掉。这个算法每次都搜索范围缩小一半，所以是一个非常快的算法。
image
上面找到立方根问题用二分搜索算法解决就是这样，
def cuberoot(n):
eps = 0.01
low = 0.0 # 下界
high = n # 上界
ans = (low + high) / 2
while abs(ans ** 3 - n) >= eps:
if ans ** 3 < n:
low = ans
else:
high = ans
ans = (low + high) / 2
if n < 0: ans *= -1
return ans
对比原来的算法可以看到，二分搜索算法快多了，原来到迭代几千次，现在十几次就行了！但是还有没有更快的算法呢？
牛顿法
牛顿法（Newton's method）又称为牛顿-拉弗森方法（Newton-Raphson method）。简单来说牛顿法可以快速的找到任何多项式的根（不光是立方根）。比如我们要找到25的平方根，首先找到一个多项式满足
，并对它求导得到
，牛顿法告诉我们如果一个数
很接近它的根，那么
就更加接近它的根。
def cuberoot(n):
eps = 0.01
g = n / 3 # 随便猜个数
while abs(g ** 3 - n) >= eps:
g = g - (g ** 3 - n) / (g ** 2 * 3)
return g
可以看到代码很紧凑，但是非常快比二分搜索算法还要快！
大O符号
上面的方法都解决同一个问题，但是速度有快有慢，那么我们怎么描述一个算法的快慢？
- 我们需要根据输入大小确定算法需要多长时间。
- 我们必须知道函数随输入大小增长的速度。
大O符号（Big O notation），又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。
大O符号描述一个算法在最坏情况下的复杂度。
比如有个累加函数
def add(n):
ans = 0
while n > 0:
ans = ans + n
n = n - 1
return ans
可以看到这个函数一共要执行步，但是大O表示法只关心当
增大时占主导地位的项目，其他项目和系数都可以忽略。这个函数用大O符号就为
是线性复杂度。
复杂度分类（从快到慢）
|符号|名称|
-|-|-
||常数|
||对数|
||多对数|
||线性|
||线性对数|
||多项式|
||指数|
||阶乘|
加法法则
比如一个函数内有两个不同复杂度的循环，
乘法法则
比如循环嵌套循环，
其他表示符号
除了大O符号还有一些不常用的符号。
大
符号
大符号（Big-Omega notation）的意思刚好和大O符号相反。大
符号表示函数在增长到一定程度时总大于一个特定函数的常数倍。不提供上限，算法最少要花多少时间。
大
符号
大符号（Big-Theta notation）是大O符号和大
符号的结合。
比如一个算法最慢为最快为
，那么用大
表示就为
，大
和大O看起来差不多，但是它们表达的意思不一样，
是表示随着
的增大函数实际增长率不会超过
，
是表示随着
的增大
就非常接近函数实际增长率。
网友评论