1.增長的階
是用來描述不同的計算過程在消耗計算資源的速率上的差異
- 令n是一個參數(shù)芬探，作為問題規(guī)模的一個度量
- 令R(n)是一個計算過程在處理規(guī)模n的問題時所需要的資源量
我們稱R(n)具有θ(f(n))的增長階恨旱，記為：
R(n) = θ(f(n))
如果存在與n無關(guān)的整數(shù)k1和k2狈涮，使得：k1f(n) <= R(n) <= k2f(n)
對于足夠大的n烹俗，值
R(n)總位于k1f(n)和k2f(n)之間
增長的階為我們提供了對計算過程行為的一種很粗略的描述玻募，也為預(yù)期一個計算過程的行為變化提供了有用的線索
2.求冪
從對一個給定的數(shù)計算乘冪的問題入手斤吐，這一過程的參數(shù)為基數(shù)b和一個正整數(shù)的指數(shù)n辕漂，過程計算出b^n浦妄，定義如下：
b^n = b * b^(n-1)
b^0 = 1
可以直接轉(zhuǎn)為一個線性的遞歸計算過程：
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
上面過程需要θ(n)步和θ(n)空間尼摹，還可以轉(zhuǎn)為一個等價的線性迭代：
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter sum)
(if (= counter 0)
sum
(expt-iter b
(- counter 1)
(* b sum))))
這一版本需要θ(n)步和θ(1)空間
此外，我們還可以借助于連續(xù)求平方去完成一般的乘冪計算：
b^n = (b^(n/2))^2 # n為偶數(shù)
b^n = b * b^(n-1) # n為奇數(shù)
將上面規(guī)則定義為過程：
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (even? n)
(= (remainder n 2) 0))
這一過程的增長的階是對數(shù)增長的
3.最大公約數(shù)（GCD）
兩個整數(shù)a和b的最大公約數(shù)定義為：能除盡這兩個數(shù)的那個最大的整數(shù)
找到兩個整數(shù)的GCD除了因式分解剂娄，還有下面的著名算法：
基本思想：如果r是a除以b的余數(shù)蠢涝，那么a和b的公約數(shù)正好是b和r的公約數(shù)
即GCD(a, b) = GCD(b, r)
從任意兩個正整數(shù)開始反復(fù)執(zhí)行這種歸約，最終將產(chǎn)生出一個數(shù)對阅懦，其中第二個數(shù)是0和二，第一個數(shù)則為GCD，這一計算方法稱為歐幾里得算法耳胎，寫成過程如下：
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
這將產(chǎn)生一個迭代計算過程惯吕，其步數(shù)依所涉及的數(shù)的對數(shù)增長
lame定理：如果歐幾里得算法需要用k步計算出一對整數(shù)的GCD，那么這對數(shù)中較小的那個數(shù)必然大于或者等于第k個斐波那契數(shù)
根據(jù)lame定理怕午，可以做出歐幾里得算法的增長階估計：
- n為較小數(shù)
- k為計算過程所需步數(shù)
- 得出
n >= Fib(k)≈φ^k / √￣5
這樣废登，步數(shù)k的增長就是n的對數(shù)(底為φ)，算法增長階為θ(log n)
