第1章 算法之美
1.1 想象算法的美
说到算法，我们想到的是什么，无论你想到的是什么，我希望你想到的是躺在法国普罗旺斯小镇的长椅上，呷(xia)一口红酒，闭上眼睛，体会舌尖上的美味，感受鼻腔中满溢的薰衣草的芳香…
1.2 算法特点
写一个算法，求如下序列之和：
− 1 , 1 , − 1 , 1 , . . . , ( − 1 ) n -1,1,-1,1,...,(-1)^n−1,1,−1,1,...,(−1) n
常见的算法就是写一个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次循环才能获得结果，其时间复杂度为O ( n ) O(n)O(n)，高斯所用的方法中，对于n条数据，需要执行1次，即复杂度为常数。
大O OO符号表示法中，时间复杂度的公式是： T ( n ) = O ( f ( n ) ) T(n) = O( f(n) )T(n)=O(f(n))，其中f ( n ) f(n)f(n) 表示每行代码执行次数之和，而 O OO 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。常见的时间复杂度包括：
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
针对算法时间复杂度，还可以分为
空间复杂度：算法在运行过程中占用的空间大小，包括：
输入输出数据
算法本身
额外需要的辅助空间
输入/输出数据占用的空间是必须的，算法本身占用的空间可以通过精简算法来缩减，但缩减的量很有限。算法在运行时所使用的辅助变量占用的空间（辅助空间）才是衡量算法空间复杂度的关键因素。
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 ( n ) T\left(n\right)T(n)为：
算法改进
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 ) O(n)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
