引入

Fibonacci

指數(shù)Version

function fib(n)
if n=0: return 0
if n=1: return 1
return fib(n-1) + fib(n-2)

包含大量重復(fù)計(jì)算步驟，基本操作次數(shù)為n的指數(shù)

線性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]

對(duì)中間計(jì)算結(jié)果進(jìn)行存儲(chǔ)，基本操作次數(shù)為關(guān)于n的線性

對(duì)數(shù)Version

^1
到
^n
在二叉樹上需要logn次上升操作

這里用到分治思想，與快速求指數(shù)類似。

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)

通項(xiàng)公式

1. 構(gòu)造
   
   的等比數(shù)列，即 - rF(n-1) = s(F(n-1) - rF(n-2)))
   可得到 - rF(n-1) = s^{n-1}(F(1) - rF(0)))
2. 則 = s^{n-1} + rF(n-1) = s^{n-1} + rs^{n-2} + rF(n-2) = s^{n-1} + rs^{n-2} + r^2*s{n-3} + ... + r^{n-2}s + r^{n-1}s^0)，即為首項(xiàng)為
   
   ，比值為
   
   的等比數(shù)列，因此
    = s^{n-1}* \frac {(r/s)^n-1} {r/s - 1})
3. 又因，因此，s/r為。因此，約簡后， = \frac {\sqrt 5} 5 [(\frac {1+\sqrt 5} 2)^n - \frac {1-\sqrt 5} 2)^n])

大O表示法

在機(jī)器無關(guān)性下分析算法

大O表示法

各函數(shù)規(guī)模增長情況

一些經(jīng)驗(yàn)規(guī)則：

1. 常系數(shù)可以忽略

2. 當(dāng)a>b時(shí)，
   
   支配
   

3. 任何指數(shù)項(xiàng)支配任何多項(xiàng)式項(xiàng)，如
   
   支配
   

4. 任何多項(xiàng)式項(xiàng)支配對(duì)數(shù)項(xiàng)，如n支配
   

對(duì)數(shù)的性質(zhì)（換底公式）：
隨著規(guī)模n的增大，對(duì)數(shù)的底對(duì)于算法復(fù)雜度并無實(shí)際貢獻(xiàn)，如 = 19.9316, log_3(1, 000, 000) = 12.5754...)
因此，在大O符號(hào)下，基數(shù)可以忽略，因此可以簡單記為O(logn)

一些公式

(2N+1)} 6 = \frac {N^3} 3)
when k!= 1,

遞歸

基本法則

1. 基準(zhǔn)情形：必須總要有某些基準(zhǔn)的情形，它們不用遞歸就能求解
2. 不斷推進(jìn)：對(duì)于那些要遞歸求解的情形，遞歸調(diào)用必須總能夠朝著一個(gè)基準(zhǔn)情形推進(jìn)

在求解一個(gè)問題的同一實(shí)例時(shí)，切勿在不同的遞歸調(diào)用中做重復(fù)性的工作