第一章：算法概述

1、算法分析與設(shè)計算法分析與設(shè)計 Algorithm Design i2; 2) while in do 3) if MAX0，存在正數(shù) 和n0 0使得對所有nn0有：0cg(n)f(n) 等價于f(n)/g(n)，as n。 f(n)(g(n) g(n)o(f(n) 1.6 算法復(fù)雜性分析算法復(fù)雜性分析 漸近分析記號的若干性質(zhì) （1）傳遞性： f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)； f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)； f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)； f(n)=(g(n)，g(n)=(h(n) f(n)

2、=(h(n)； f(n)=(g(n)，g(n)=(h(n) f(n)=(h(n)； （2）反身性： f(n)=(f(n)；f(n)=(f(n)；f(n)=(f(n). （3）對稱性： f(n)=(g(n) g(n)=(f(n) . （4）互對稱性： f(n)=(g(n) g(n)=(f(n) ；f(n)=(g(n) g(n)=(f(n) ； （5）算術(shù)運算： (f(n)+(g(n) = (maxf(n),g(n) ； (f(n)+(g(n) = (f(n)+g(n) ；(f(n)*(g(n) = (f(n)*g(n) ； (cf(n) = (f(n) ；g(n) = (f(n) (f(n)+(

3、g(n) = (f(n) 。 1.6 算法復(fù)雜性分析算法復(fù)雜性分析 規(guī)則(f(n)+(g(n) = (maxf(n),g(n) 的證明： 對于任意f1(n) (f(n) ，存在正常數(shù)c1和自然數(shù)n1，使得 對所有n n1，有f1(n) c1f(n) 。 類似地，對于任意g1(n) (g(n)，存在正常數(shù)c2和自然數(shù) n2，使得對所有n n2，有g(shù)1(n) c2g(n) 。 令c3=maxc1, c2，n3 =maxn1, n2，h(n)= maxf(n),g(n) 。 則對所有的n n3，有 f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(

4、n) + g(n) c32 maxf(n),g(n) 2c3h(n) (maxf(n),g(n). 1.6 算法復(fù)雜性分析算法復(fù)雜性分析 取整函數(shù) x ：不大于x的最大整數(shù)； x ：不小于x的最小整數(shù)。 取整函數(shù)的若干性質(zhì) x-1 x x x 0，有： n/a /b = n/ab ; n/a /b = n/ab ; a/b (a+(b-1)/b; a/b (a-(b-1)/b; 其中，f(x)= x , g(x)= x 為單調(diào)遞增函數(shù)。 1.6 算法復(fù)雜性分析算法復(fù)雜性分析 算法分析中常見的復(fù)雜性函數(shù) 1.6 算法復(fù)雜性分析算法復(fù)雜性分析 小規(guī)模數(shù)據(jù)復(fù)雜性增長圖 1.6 算法復(fù)雜性分析算法復(fù)雜

5、性分析 中等規(guī)模數(shù)據(jù)復(fù)雜性增長圖 小結(jié)小結(jié) 程序與算法 漸進(jìn)表達(dá)式 程序復(fù)雜性 （1）選擇語句：）選擇語句： （1.1) if 語句：語句： （1.2) ？語句：？語句： if (expression) statement; else statement; exp1?exp2:exp3 y= x9 ? 100:200; 等價于： if (x9) y=100; else y=200; （1.3) switch語句：語句： switch (expression) case 1: statement sequence; break; case 2: statement sequence; break

6、; default: statement sequence; （2）迭代語句：）迭代語句： （2.1) for 循環(huán)：循環(huán)： for (init;condition;inc) statement; （2.2) while 循環(huán)：循環(huán)： while (condition) statement; （2.3) do-while 循環(huán)：循環(huán)： do statement; while (condition); （3）跳轉(zhuǎn)語句：）跳轉(zhuǎn)語句： （3.1) return語句：語句： return expression; （3.2) goto語句：語句： goto label; label: （4）函數(shù)：）函數(shù)

7、： 例：例： return-type function name(para-list) body of the function int max(int x,int y) return xy?x:y; （5）模板）模板template ： template Type max(Type x,Type y) return xy?x:y; int i=max(1,2)； double x=max(1.0,2.0)； （6）動態(tài)存儲分配： （6.1）運算符）運算符new ： 運算符new用于動態(tài)存儲分配。 new返回一個指向所分配空間的指針。 例：int x；y=new int；y=10； 也可將上述

8、各語句作適當(dāng)合并如下： int y=new int；y=10； 或 int y=new int(10)； 或 int y；y=new int(10)； （6.2）一維數(shù)組）一維數(shù)組 ： 為了在運行時創(chuàng)建一個大小可動態(tài)變化的一維浮點數(shù)組x，可先將x聲 明為一個float類型的指針。然后用new為數(shù)組動態(tài)地分配存儲空間。 例：例： float x=new floatn； 創(chuàng)建一個大小為n的一維浮點數(shù)組。運算符new分配n個浮點數(shù)所需的 空間，并返回指向第一個浮點數(shù)的指針。 然后可用x0，x1，xn-1來訪問每個數(shù)組元素。 （6.3）運算符）運算符delete ： 當(dāng)動態(tài)分配的存儲空間已不再需要時應(yīng)及時釋放所占用的空間 。用運算符delete來釋放由new分配的空間。 例：例： delete y； delete x； 分別釋放分配給y的空間和分配給一維數(shù)組x的空間。 （6.4）動態(tài)二維數(shù)組）動態(tài)二維數(shù)組 ： 創(chuàng)建類型為Type的動態(tài)工作數(shù)組，這個數(shù)組有rows行和cols 列。 template void Make2DArray(Type* for (int i=0;irows;i+) xi=new Typecols; 當(dāng)不再需要一個動態(tài)分配的二維數(shù)組時，可按以下步驟釋放它所占