上一篇的递归算法中,了解到算法的复杂度。递归就是在函数中调用本身。
在汉诺塔游戏例子中,如果你需要移动的盘子很多时,程序运行就会消耗很长时间来计算结果。可以回顾下 —>算法篇-python递归算法
用递归打印斐波那契数列,你会发现,即使n只有几十的时候,你的计算机内存使用量已经飙升了。
可以结合 生成器 优化下程序,不管n有多大,都不会出现卡顿。
有一点,关于递归次数,python中有个限制,可以通过sys模块来解决。
python 查找算法
查找就是根据给定的某个值,在查找表中确定一个关键字等于给定值的数据元素。
知道了查找的定义,试着用一个简单的例子,能想到 for 循环么?
有没有发现,是不是两两比较就能找到啦。假设列表中有很多元素,再用 for 循环来查找,得到结果的时间会不会更长。
算法的复杂度是渐进的,即对于一个大小为n的输入,如果它的运算时间为n3+5n+9,那么它的渐进时间复杂度是n3
刚刚用的 for 循环 来查找,它的时间复杂度O(n)
有没有继续优化的查找算法呢?
可以设想下,在列表中元素能一半一半的查找,再来查找目标值,是不是就会快一些。
接着就是~
二分查找
上面说到,一半一半的查找,看目标值在左边一半还是右边一半,然后替换左端点或者右端点,继续判断。
直接上例子啦