A演算法期中考(上)

演算法筆記

(小考摘要/ch-1,2)

1.è徵求註解?

Let f(n)=n, g(n)=n^2

Min(f(n),g(n))=n     //

Theta(f(n)+g(n))=theta(n+n^2)=theta(n^2)   //n不見了?

→Min(f(n)),g(n))→!=theta(f(n)+g(n))

當n值很大的時候n^2的值會超級大 大到可以忽略n值了

所以就沒有寫n

就像n^2+3n+1 若只是要求近似值就只看n^2的值

2.èbig-oh代入法

Let f(n)=1, g(n)=n          //

Suppose g(n)=O(f(n))

→g(n)<=C f(n)          //將O(f(n))=代成<=C f(n)

n/1<=C*              //啥意思?可以省略嗎?

n<=C                //

3.èbig-oh代入法

f(n)=O((f(n))^2)       //

Let f(n)=1/n

→f(n)<=C*(f(n))^2      //O( )=代成<=C*

1/n <=C*1/(n^2)

(n^2)/n <=C

N<=C

4.èbig-oh代入法

Let f(n)=2n

g(n)=n

Suppose 2^f(n) =O(2^g(n))

→2^f(n) <=C*2^g(n)          //O( )=代成<=C*

2^(2n) <=C*(2^n)

(4/2)^2n <=C*(2^n)           //?

→(2^n)(2^n) <=C*(2^n)

2^n <=C →(4/2)^n <=C

5.ètheta代入法

f(n)= theta(f(n/2))

→f(n) <=C*f(n/2)   //=theta( )代成 <=C*

If f(n)=2^n                             // 2^n <= C*(2^(n/2)) =(2^(1/2)) ^n→(2/(SR.2))^n <=C

→2^n <= C*2^(n/2)=( 2^1/2 )^n = (SR.2)^n    //

(2/1)^n <=C(SR.2)^n

→(2/(SR.2))^n <=C

(問答題)

在排序分析中，通常最好的狀況是輸入的資料「已經排序過」，最差的狀況是「剛好反向」的順序，但是一般來說，輸入的資料應該介於這兩者之間。不過我們大部份著重在尋找最差情況的執行時間，也就是任何輸入量n的最長執行時間，請問理由為哪三個？

è

1.最保險，確保執行過程沒有更壞的情況。

2.最差情況常常發生時：如所尋資料不在該資料庫中。

3.平均情況與最差情況一樣糟。

(資料結構與排序、堆積/ch-3,4,5)

(習題與補充)

1.背包問題 (0/1 knapsack problem)

2.複雜度分析(complexity analysis)

3.遞迴公式(Recursion)

a.代入法SubstitutionM*2

(a1)  set f(n)={f(n-1)+c1→if n>=1; c2 →if n=0 } ask f(n)=?

→f(n)=f(n-1)+c1

=(f(n-2)+c1)+c1

=f(n-2)+2c1

.....

=f(n-3)+3c1

.....

=f(0)+Nc1

=c2+Nc1

(a2)set f(n){f(n/2)+c1 if n=(2^k),k>=1 ; c2 if n=1} ask f(n)=?

let n=(2^k)  also k=log_2 N

f(n)=f(n/2)+c1=(f(n/(2^2))+c1)+c1=f(n/(2^2))+2c1

.....

f(n/(2^2))+kc1=f(1)+kc1=c2+kc1=c2+c1log_2 N,N>=1

(a3)階乘的遞迴呼叫

a3.1定義：n!={1,if n=0; n*(n-1)!, if n>0}

a3.2程式Code：

{int f;

if(n==0) return 1;  //終止條件

f=fact(n-1);  //遞迴呼叫

return (n*f);

}

b.歸納法InductionM

(b1) Fibonacci數列

定義：Fib(n)={0,if n=0;1,ifn=1;Fib(n-1)+Fib(n-2),if n>=2}

程式Code：

int Fib(int n)

{

 int i,j;

if(n==0)

return(0)  //end condition: n=0

if(n==1)

return(1) //e.c. :n=1

i=Fib(n-1);

j=Fib(n-2);

return (i+j);

}

(c.特徵多項式法)

ex.二項式係數

公式： c(n,k)=(n!/k!(n-k)!)

定義：c(n,k)={1.if k=0 or k=n};  c(n-1,k-1)+c(n-1,k), if n>k>0}

程式Code：

int C(int n, int k)

{

if(k==0 || k==n)return 1;   //e.c.

return (C(n-1,k-1)+C(n-1,k));  //recursive calling

}

(計算複雜度/黃ch8.6)

1.定義.9

2.Note.14

3.定理.8

4.定理.9

5.Note.15

6.定理.10

7.推廣.3

8.Note.16

1.è定義.9

2.èNote.14

a. f(n)=O(g(n))有時寫成f(n)O(g(n))

b. f(n)=Θ(g(n)) <=>f(n)=O(g(n))且f(n)=Ω(g(n))

c. 複雜度種類

C1.常級O(1)   //constant

C2.對級O(lg n)  //O(log2 n), logarithmic

C3.線性級O(n)   //linear

C4.線性對級O(n lg n)  //O(n log2 n),log linear

C5.平方級O(n^2)   //quadratic

C6.立方級O(n^3)   //cubic

C7.多項式級O(n^m),m=0,1,2…  //polynomial

C8.指數級O(C^n), c>1  //exponential

C9.階乘級O(n!)  //factorial

d. f(n)=O(g(n))指除有限項外，g(n)為f(n)的上界，即g(n)的成長速率至少與f(n)一樣快，但求g(n)時我們都要求找最小上界，例如上例中按定義寫成f(n)=O(n^3)或f(n)=O(2^n)皆可β.→平方級f(n)=O(n^2)才最適

e. f(n)=Ω(g(n))指除有限項外，g(n)為f(n)的下限，即 f(n)的成長速率至少與 g(n)     一樣快，同理求 g(n)時一般要求找最大下界

f. f(n)=Θ(g(n))可看成 f(n)與g(n)的成長速率一樣快

3.è定理.8

4.è定理.9 set f(n)=(AkN^k)+(A(k-1)N^(k-1))+…..+A1N+A0, above A0,…,Ak R

and Ak>0, then …

(1) f(n)=Ω(n^k)

(2) f(n)=Θ(n^k)

4aè.例19.(2)→g(n)=Θ(n^2)

(線性級=平方級取theta)

4bè.例20. prove→lg.2(n!)=Θ(n lg n)

(階乘對數=線性對數級取theta)

4cè.例21. prove→lg.a N=Θ(lg.b N)

(a底對數=b底對數取theta)

5è.Note.15

→f(n)=O(g(n))

→f(n)=Ω(g(n))

5aè.T(n)=O(2^n)   //指數級取big-O

6è.定理.10

→if  f1(n)=O(g1(n)),f2(n)=O(g2(n)) then

(1)→二函數和(f1+f2)(n)=O(max(g1(n),g2(n)))

(2)→二函數積(f1f2)(n)=O(g1(n)g2(n))

7è.推廣.3

If  f1(n)=O(g(n)), f2(n)=O(g(n)), then N的二函數和(f1+f2)(n)=O(g(n)) //G函數取big-O

8è.Note.16

8aè.which of following is the largest as n→∞

(1)n^100,(2)2^n,(3)(ln n)^n,(4)n^(SR<n>)→N的(N平方根)次方,(5)n!

→將這些函數 “取log”得：

lg(n^100)=100 lg(n),

lg(2^n)=n lg(2),

lg(ln(n)^n)=n lg(lg(n)),

lg(n^(SR<n>))=SR<n> lg(n),

lg(n!)=Θ(n lg n)

//N階取log=n lg n取theta

所以成長速率最快者為第五的 “n!”

(黃補)

一、計算複雜度(黃ch-8.6)

二、遞迴式(ch-5.1,2)

六、搜尋樹(ch-7.5)

(謝補)

三、基本形式

四、排序

五、堆積heap ?

七、雜湊

(目次)

一、簡介

1.特性

2.步驟

3.表示

4.正確性

5.效能評估

6.最佳化

//黃ch-8 (三大演算法、傳輸網、配對論、複雜度)

二、效能

1.概說

2.時間複雜度(theta, big-O,omega)   //黃ch-8

3.空間複雜度

4.遞迴公式(取代、支配)   

//黃ch-5(關係式、基礎遞迴關係、轉換法求解、生成函數法求解、應用與其他)

三、基本形式(DS)  //謝ch-3,4

1. linked-list

2. stack

3. queue

4. BinaryTree

5.summary

四、排序sorting   //謝ch-7

1.基本法(選擇、氣泡、插入)

2.合併法

3.快速法

4.線性時序

5.小結

五、堆積heap  //?

1.概說

2.建立

3.堆積排序

4,優先權佇列

5,小結

六、搜尋樹searchingTree   //謝ch-6,8

1.線性搜尋

2.BS

3.BST

4.平衡樹(AVLT, RBT, BT)

5.小結

//黃ch-7(樹概說、有根、生成、最小生成、搜尋樹)

七、雜湊hash   //謝

1.雜湊函數

2.碰撞問題

3.單向

4.小結

期中考

(八、字串搜尋)

九、圖論          //黃ch-6

十、加權圖

(十一、網路流)

十二、貪婪演算法

十三、動態程序規畫

十九、NP完全的問題

(十四、回溯與分支設限)

(十五、數論)

(十六、計算幾何)

(十七、矩陣)

(十八、多項式與FFT)

(廿、平行演算法)