趣味算法-03-跟着作者读《趣味算法（第2版）》-算法之美
趣味算法-03-跟着作者读《趣味算法（第2版）》-算法之美
努力是为了不平庸算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！
趣味算法-03-跟着作者读《趣味算法（第2版）》-算法之美
- [系列博客：](https://cloud.tencent.com/developer)
- [第1章 算法之美](https://cloud.tencent.com/developer)
- [1.1 想象算法的美](https://cloud.tencent.com/developer)
- [1.2 算法特点](https://cloud.tencent.com/developer)
- [1.3 算法的时间和空间复杂性](https://cloud.tencent.com/developer)
- [1.4 神奇的兔子序列](https://cloud.tencent.com/developer)
- [算法题目来源](https://cloud.tencent.com/developer)
- [算法题目描述](https://cloud.tencent.com/developer)
- [做题思路](https://cloud.tencent.com/developer)
- [模板代码](https://cloud.tencent.com/developer)
- [做题过程中遇到的bug及解决方案](https://cloud.tencent.com/developer)
- [时间复杂度计算](https://cloud.tencent.com/developer)
- [算法改进](https://cloud.tencent.com/developer)系列博客：
本文是系列博客的第3篇，是听了陈老师的报告后的记录，主要包括如何学习算法。
第1章 算法之美
1.1 想象算法的美
说到算法，我们想到的是什么，无论你想到的是什么，我希望你想到的是躺在法国普罗旺斯小镇的长椅上，呷(xia)一口红酒，闭上眼睛，体会舌尖上的美味，感受鼻腔中满溢的薰衣草的芳香…
1.2 算法特点
写一个算法，求如下序列之和：
常见的算法就是写一个while循环，然后依次相加即可，这种方式可以求得结果，但需要计算n次：
arr = [-1,1,-1,1,-1]
arr_sum = 0
for i in range(1,len(arr)+1):
arr_sum += pow(-1,i)
print(arr_sum)如果采取-1+1 = 0 ，如果长度为偶数，结果为0，否则为-1：
arr = [-1,1,-1,1,-1]
arr_sum = 0
arr_len = len(arr)
if (arr_len % 2==0):
print(0)
else:
print(-1)第一种算法需要执行n次，第二种算法需要执行1次，后者就是数学家高斯所使用的算法。
需要说明的是，笨方法也是算法，高斯使用的方法也是算法。
算法具有如下特性：
- 有穷性：算法是若干质量组成的又穷序列，总是会执行若干次后结束
- 确定性：每条语句都有明确的含义，无歧义
- 可行性：算法再当前环境条件下可以通过有限次运算来实现
- 输入/输出：有0或多个输入以及1个或多个输出
好的算法的标准：
- 正确性：正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期。
- 易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。
- 健壮性:算法对非法数据及操作有较好的反应和处理。例如,在学生信息管理系统中登记学生年龄时,若将21岁误输入为210岁,则系统应该有错误提示。
- 高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。
- 低存储性:低存储性是指算法所需的存储空间小。对于像手机、平板电脑这样的嵌入式设备,算法如果占用空间过大,则无法运行。算法占用的空间大小被称为空间复杂度。
正确性，易读性，健壮性是在我们完成了算法的基础上，适当提高下工程标准即可。但时间复杂度和空间复杂度的优化就有一定的难度了。
1.3 算法的时间和空间复杂性
时间复杂度是按照计算机支持的次数来衡量的，如上面的例子中，笨方法中，对于n条数据，需要执行n次循环才能获得结果，其时间复杂度为
，高斯所用的方法中，对于n条数据，需要执行1次，即复杂度为常数。
大
符号表示法中，时间复杂度的公式是：
，其中
表示每行代码执行次数之和，而
表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。常见的时间复杂度包括：
常数阶
对数阶
线性阶
线性对数阶
平方阶
立方阶
K次方阶
指数阶
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
针对算法时间复杂度，还可以分为
常数阶：
可以是2,20,100
多项式阶：
比较常见
指数阶：
要避免指数阶！！
对数阶:
效率较高
随n的增长，时间复杂度增加的关系如下：
空间复杂度：算法在运行过程中占用的空间大小，包括：
- 输入输出数据
- 算法本身
- 额外需要的辅助空间
输入/输出数据占用的空间是必须的，算法本身占用的空间可以通过精简算法来缩减，但缩减的量很有限。算法在运行时所使用的辅助变量占用的空间（辅助空间）才是衡量算法空间复杂度的关键因素。
1.4 神奇的兔子序列
假设第1个月有1对初生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的免子每月会生1对兔子,兔子永不死去.那么,由1对初生的免子开始, 12个月后会有多少对兔子呢? 兔子数列即斐波那契数列,它的发明者是意大利数学家莱奥纳尔多斐波那契(Leonardo Fibonacci, 1170-1250) 。1202年,莱奥纳尔多撰写了《算盘全书》(Liber Abaci),该书是一部较全面的初等数学著作。书中系统地介绍了印度一阿拉伯数码及其演算法则,以及中国的“盈不足术”;此外还引入了负数,并研究了一些简单的一次同余式组。
提示：简单描述OR总结所学习的算法知识点，可列举文字/图片/视频教程
算法题目来源
《趣味算法第2版》斐波那契数列 问题
算法题目描述
假设第1个月有1对初生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的免子每月会生1对兔子,兔子永不死去.那么,由1对初生的免子开始, 12个月后会有多少对兔子呢? 兔子数列即斐波那契数列,它的发明者是意大利数学家莱奥纳尔多斐波那契(Leonardo Fibonacci, 1170-1250) 。1202年,莱奥纳尔多撰写了《算盘全书》(Liber Abaci),该书是一部较全面的初等数学著作。书中系统地介绍了印度一阿拉伯数码及其演算法则,以及中国的“盈不足术”;此外还引入了负数,并研究了一些简单的一次同余式组。
做题思路
把上面的数列用图展示：
这个数列的特点是：
模板代码
def fib(n):
if (n==1 or n ==2):
return 1
return fib(n-1) + fib(n-2)
x = fib(3)
print(x)做题过程中遇到的bug及解决方案
目前实现了算法，但没有考虑时间复杂度，如何快速的找到数列的内在规律，并结合算法设计，需要日积月累的努力，切不可大意。
时间复杂度计算
针对斐波那契数列，上面模板中时间复杂度T\left(n\right) 为：
算法改进
def fib2(n):
if n <2 :
return 1
list1 = [1 for x in range(0,n)]
for i in range(2,n):
list1[i] = list1[i-1] + list1[i-2]
print(list1)
return list1[n-1]
x = fib2(3)
print(x)这种算法中，时间复杂度从指数阶 降到了 O(n) ，效率提升了很多
题外话：
斐波那契数列的最后两项比值接近于0.618黄金分割
1÷1 = 1 1÷2 = 0.5 2÷3 = 0.66 3÷5 = 0.6 5÷8 = 0.624 … 55÷89 = 0.6117977 … 144÷233 = 0.618025