引入
Fibonacci
指数Version
function fib(n)
if n=0: return 0
if n=1: return 1
return fib(n-1) + fib(n-2)
包含大量重复计算步骤，基本操作次数为n的指数
线性Version
function fib(n)
if n=0: return 0
create an array f[0...n]
f[0]=0, f[1]=1
for i=2...n:
f[i]=f[i-1]+f[i-2]
return f[n]
对中间计算结果进行存储，基本操作次数为关于n的线性
对数Version
^1
到
^n
在二叉树上需要logn次上升操作
这里用到分治思想，与快速求指数类似。
function power(a, n)
if(n=0) return 1
x = power(a, n/2's floor)
if(n is even)
then return(x^2)
else
return (a*n^2)
通项公式
- 构造的等比数列，即 - rF(n-1) = s(F(n-1) - rF(n-2)))
可得到 - rF(n-1) = s^{n-1}(F(1) - rF(0))) - 则 = s^{n-1} + rF(n-1) = s^{n-1} + rs^{n-2} + rF(n-2) = s^{n-1} + rs^{n-2} + r2*s{n-3} + ... + r^{n-2}s + r^{n-1}s^0)，即为首项为，比值为的等比数列，因此
 = s^{n-1}* \frac {(r/s)^n-1} {r/s - 1}) - 又因，因此，s/r为。因此，约简后， = \frac {\sqrt 5} 5 [(\frac {1+\sqrt 5} 2)^n - \frac {1-\sqrt 5} 2)^n])
大O表示法
在机器无关性下分析算法
一些经验规则：
- 常系数可以忽略
-
当a>b时，支配
-
任何指数项支配任何多项式项，如支配
-
任何多项式项支配对数项，如n支配
对数的性质（换底公式）：
随着规模n的增大，对数的底对于算法复杂度并无实际贡献，如 = 19.9316, log_3(1, 000, 000) = 12.5754...)
因此，在大O符号下，基数可以忽略，因此可以简单记为O(logn)
一些公式
(2N+1)} 6 = \frac {N^3} 3)
when k!= 1,
递归
基本法则
- 基准情形：必须总要有某些基准的情形，它们不用递归就能求解
- 不断推进：对于那些要递归求解的情形，递归调用必须总能够朝着一个基准情形推进
在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作
