計(jì)算機(jī)算法設(shè)計(jì)與分析--第1章算法概述-資料下載頁(yè)
2024-10-19 10:17本頁(yè)面
【正文】 T n n n n T n n n T n n T n T k k k ? 180。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L 遞歸算法分析 例 2： 54 例線性對(duì)數(shù)階 O(log2n )： i=1。 ① ? while (i=n) ? i=i*2。 ② ?解： 語(yǔ)句 1的頻度是 1, ? 設(shè)語(yǔ)句 2的頻度是 f(n), 則：2^f(n)=n。f(n)=log2n ? 取最大值 f(n)= log2n, ? T(n)=O(log2n ) 55 Ο(1) 稱為常數(shù)級(jí) Ο(logn) 稱為對(duì)數(shù)級(jí) Ο(n) 稱為線性級(jí) Ο(n c)稱為多項(xiàng)式級(jí) Ο(c n)稱為指數(shù)級(jí) Ο(n!) 稱為階乘級(jí) (n為問(wèn)題的規(guī)模 ,c為一常量 ) 算法復(fù)雜性的一般表示形式 低 高 時(shí)間復(fù)雜性 56 提綱 一、算法與程序 二、算法復(fù)雜性分析 三、用 C++語(yǔ)言描述算法的方法 57 用 c++描述算法 58 ? （ 1）選擇語(yǔ)句： ? （ ) if 語(yǔ)句： ? （ ) ？語(yǔ)句： ? if (expression) statement。 else statement。 exp1?exp2:exp3 y= x9 ? 100:200。 等價(jià)于： if (x9) y=100。 else y=200。 59 （ ) switch語(yǔ)句： switch (expression) { case 1: statement sequence。 break。 case 2: statement sequence。 break。 ? default: statement sequence。 } 60 （ 2）迭代語(yǔ)句： ? （ ) for 循環(huán)： ? for (init。condition。inc) statement。 ? （ ) while 循環(huán)： ? while (condition) statement。 ? （ ) dowhile 循環(huán)： ? do{ ? statement。 ? } while (condition)。 61 （ 3）跳轉(zhuǎn)語(yǔ)句： ? （ ) return語(yǔ)句： ? return expression。 ? （ ) goto語(yǔ)句： ? goto label。 ? ? ? label: 62 （ 4）函數(shù)： ? 例： returntype function name(paralist) { body of the function } int max(int x,int y) { return xy?x:y。 } 63 （ 5）模板 template ： template class Type Type max(Type x,Type y) { return xy?x:y。 } int i=max(1,2)； double x=max(,)； 64 （ 6）動(dòng)態(tài)存儲(chǔ)分配： ? （ ）運(yùn)算符 new ： ? 運(yùn)算符 new用于動(dòng)態(tài)存儲(chǔ)分配。 ? new返回一個(gè)指向所分配空間的指針。 ? 例： int ?x； y=new int； ?y=10； ? 也可將上述各語(yǔ)句作適當(dāng)合并如下： ? int ?y=new int； ?y=10； ? 或 int ?y=new int(10)； ? 或 int ?y； y=new int(10)； 65 （ ）一維數(shù)組 ： ? 為了在運(yùn)行時(shí)創(chuàng)建一個(gè)大小可動(dòng)態(tài)變化的一維浮點(diǎn)數(shù)組 x，可先將x聲明為一個(gè) float類型的指針。然后用 new為數(shù)組動(dòng)態(tài)地分配存儲(chǔ)空間。 ? 例： ? float ?x=new float[n]； ? 創(chuàng)建一個(gè)大小為 n的一維浮點(diǎn)數(shù)組。運(yùn)算符 new分配 n個(gè)浮點(diǎn)數(shù)所需的空間，并返回指向第一個(gè)浮點(diǎn)數(shù)的指針。 ? 然后可用 x[0]， x[1]， … ， x[n1]來(lái)訪問(wèn)每個(gè)數(shù)組元素。 66 （ ）運(yùn)算符 delete ： ? 當(dāng)動(dòng)態(tài)分配的存儲(chǔ)空間已不再需要時(shí)應(yīng)及時(shí)釋放所占用的空間。 ? 用運(yùn)算符 delete來(lái)釋放由 new分配的空間。 ? 例： ? delete y； ? delete [ ]x； ? 分別釋放分配給 ?y的空間和分配給一維數(shù)組 x的空間。 67 （ ）動(dòng)態(tài)二維數(shù)組 ： ?創(chuàng)建類型為 Type的動(dòng)態(tài)工作數(shù)組，這個(gè)數(shù)組有rows行和 cols列。 template class Type void Make2DArray(Type** amp。x,int rows, int cols) { x=new Type*[rows]。 for (int i=0。irows。i++) x[i]=new Type[cols]。 } 68 ? 當(dāng)不再需要一個(gè)動(dòng)態(tài)分配的二維數(shù)組時(shí)，可按以下步驟釋放它所占用的空間。首先釋放在 for循環(huán)中為每一行所分配的空間。然后釋放為行指針?lè)峙涞目臻g。 ? 釋放空間后將 x置為 0，以防繼續(xù)訪問(wèn)已被釋放的空間。 template class Type void Delete2DArray(Type** amp。x,int rows) { for (int i=0。irows。i++) delete []x[i]。 delete []x。 x=0。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1