魅力永恒的斐波那契

天朝的同学们第一次学习斐波那契总跟那些繁殖力惊人的兔子脱不开干系.当然在达尔文进化论统治的空间里这是不现实的,除非在一个自建生态系统的初始阶段.

斐波那契的第一个研究者是将近一千年前的意大利数学家Leonardo(是的,和小李子同名)Fibonacci,它的魅力在于很多优美的性质,比如相邻斐波那契数想除的商会逐渐逼近黄金比例(我不知道为什么人们都觉得黄金分隔比是美的,然而确实就是这么觉得,身在宇宙中大概天生遵守一些法则),奇数项和,偶数项和,和天然植物,蜂巢的关系… 一切都惊人般的和谐.

Then let’s get down to business.

求解优化

如果斐波那契先生在梦里问了你一个问题,第n个斐波那契是什么?

As simple and elegant as it sounds.

相信你不好意思说我在您一千年之后还不会解吧.当然,你可以说啊,不如我们来谈谈star war……

O(2^n)

斐波那契是dynamic programming 方法的经典案例之一,第一反应自然是recursion.正如它的定义

1
2
3

f(0)=1
f(1)=1
for n>=2 f(n) = f(n-1)+f(n-2)

#using python
def fibonacci(n):
	if n==0:
		return 0
	elif n==1:
		return 1
	else:
		return fibonacci(n-1)+fibonacci(n-2)

最自然的解法.然而时间复杂度是O(2^n)很慢,因为把其他事情都丢给计算机去做了,只是把定义转义了一下.
为什么很慢,当call f(n) = f(n-1)+f(n-2) 会分头去计算f(n-1),f(n-2) 而f(n-1)会用到 f(n-2), f(n-1)和f(n-2)都会用到f(n-3),所有计算的中间结果都被浪费掉了.巨人的肩膀就在那里,偏偏要自己从头再来. 想起<<三体>> 中的乱纪元,如果当所有恒纪元中积累的文明都被摧毁,下一个乱纪元一切都会重头再来.从这一点上来看,人类是幸运的.n越小的因子被重复计算的次数越多

F(6)                 *  
F(5)                 *  
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

被计算的次数在指数性增长.得到一棵深度为n-1的树.

O(n)

那么我要站在巨人的肩膀上,把文明通过历史的方式流传下去. 也就是要把计算结果储存起来,避免重复计算, 只有n个数,那我需要一个长度为n的list.
这同时也是 DP的bottom-up 的形式,从底层算起,直至找到目标.
可以写成一个for-loop 这样还可以避免递归function call的损耗

def fibonacci(n):
	fibs = []
	fibs.append(0)
	fibs.append(1)
	for i in range(2,n+1):
		fibs.append(fibs[i-1]+fibs[i-2])
		
	return fibs[n]

也可以top-down递归


class beauty:
	def __init__(self,n):
		self.fibs = [-1 for i in range(0,n+1)]
		self.n = n
	def fibonacci(self,n):
		if self.fibs[n]!=-1 :
			return fibs[n]
	
		if n==0:
			fibs[n]=0
		elif n==1:
			fibs[n]=1
		else:
			fibs[n] = fibonacci(n-1)+fibs(n-2)
	
		return fibs[n]

在巨人的肩膀上,轻松得到了linear time complexity.

还可以再优化吗?

看一下需求,斐波那契先生只问你第n个数是什么,没有问你从第一个到第n个是哪些数, 也就是说你的工作结果超过了他的需求(…不要类比产品经理,因为斐波那契比我们更懂斐波那契),那么其他的结果,你算出的哪些f(5),f(9),..f(n-3) 从”最理想” 的角度看都是被浪费的. 有连续性的一座桥可以过河,有离散分布的鹅卵石也可以过河 ( 不排除人家裘千仞连鹅卵石都不需要就可以过河 ).也就是说,除了计算结果的必由之路都是可以省略的,(不过这个必由之路恐怕就是 casewise的了).

计算机计算乘法和加法的时间并没有很大影响,那么怎样优化用乘法呢?

O(log n )

有一个我很喜欢的matrix A

1 2	[[1,1] ,[1,0]]

这是一个通向未来又记录过去的matrix

1 2	[[f(n),f(n-1) [[1,1] [[f(n) + f(n-1), f(n)] ,f(n-1),f(n-2)]] * ,[1,0]] = ,[f(n-1)+f(n-2),f(n-1)]

不断地乘以这个matrix 会得到斐波那契增长.
同时,我们得到了乘方!

f(n) = A^n [0][0]

不再想要每步线性增长,而希望得到指数增长,(也就是增大步长,用现有最大资源来作为步长前进),对乘法来说的现有最大资源就是乘以它自己, here comes matrix exponential

如果n%2==0 n = (n/2)+(n/2)
A^n = (A^(n/2))^2
如果n%2==1 n = 1+(n-1), 替换到下个偶数即可

import numpy as np
def matrix_power(A,n):
	if n==0:
		return 1
	if n==1:
		return A
	if n%2==1:
		return A*matrix_power(A,n-1)
	
	B = matrix_power(A,n/2)
	return B*B
	
def fibonacci(n):
	if n==0:
		return 0
	if n==1:
		return 1
	A = np.matrix([[1,1],[1,0]])
	return matrix_power(A,n-1)[0,0]

空间换时间

space-time balance 是一个永远的权衡. 时间的节约很大程度上来源于我们提前将那些需要重复计算的值存储下来,用的时候只需要constant的access time.
这个叫做precomputation.

传说鱼儿的记忆只有七秒,那么它生命应该是浪费了大量的时间来重复计算和重复思考.

就像这样,你端起酒杯走向一个人准备请ta喝一杯,走到身前的时候完全忘记为什么站在这里,于是走回自己喜爱的座位.片刻之后,发现那边有个人,我想去请ta喝一杯. 然后you get into an infinite loop.

在这期间 John Nash 教授想出了博弈论 …. ( Credit to movie A beautiful mind )