計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)[王曉東][電子教案]第1章(更新版)
【正文】 elete [ ]x； ? 分別釋放分配給 ?y的空間和分配給一維數(shù)組 x的空間。首先釋放在 for循環(huán)中為每一行所分配的空間。 x=0。 // cost times for (int i = 1。 // c6 sum og (ti1) } a[j+1]=key。 ? return n*factorial(n1)。 ? 在最壞情況下， ti ? i+1, for 1 ? i n。 i++){ // c1 n key=a[i]。in。 ? 釋放空間后將 x置為 0，以防繼續(xù)訪問已被釋放的空間。 template class Type void Make2DArray(Type** amp。然后用 new為數(shù)組動(dòng)態(tài)地分配存儲(chǔ)空間。 ? } while (condition)。 case 2: statement sequence。 ? log log n = log(log n)。 ? a1 ? an為 單調(diào)遞增函數(shù) 。 ? k ? d ? p(n) = ?(nk) 。 ? ? ? n/a ? /b ? = ? n/ab ? 。 ? 類似地，對(duì)于任意 g1(n) ? O(g(n)) ，存在正常數(shù) c2和自然數(shù) n2，使得對(duì)所有 n? n2，有 g1(n) ? c2g(n) 。 ? 例如： 2n2 + 3n + 1 = 2n2 + ?(n) 表示 ? 2n2 +3n +1=2n2 + f(n)，其中 f(n) 是 ?(n)中某個(gè)函數(shù)。 ? t(n)是 T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。 ? 例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。 ? 掌握用 C++語(yǔ)言描述算法的方法。 ? 掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。 ? 程序可以不滿足算法的性質(zhì) (4)。 ? (T(n) t(n) )/ T(n) ?0 ， as n??。 ? 一般情況下，等式和不等式中的漸近記號(hào) ?(g(n))表示?(g(n))中的某個(gè)函數(shù)。 ? 規(guī)則 O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的 證明： ? 對(duì)于任意 f1(n) ? O(f(n)) ，存在正常數(shù) c1和自然數(shù) n1，使得對(duì)所有n? n1，有 f1(n) ? c1f(n) 。 ? 對(duì)于 n ? 0， a,b0，有： ? ? ? n/a ? /b ? = ? n/ab ? 。 ? k ? d ? p(n) = O(nk) 。 ? aman = am+n 。 ? logkn = (log n)kl。 break。 ? （ ) dowhile 循環(huán)： ? do{ ? statement。 ? 例： 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)； （ ）一維數(shù)組 ： ? 為了在運(yùn)行時(shí)創(chuàng)建一個(gè)大小可動(dòng)態(tài)變化的一維浮點(diǎn)數(shù)組 x，可先將x聲明為一個(gè) float類型的指針。 （ ）動(dòng)態(tài)二維數(shù)組 ： ? 創(chuàng)建類型為 Type的動(dòng)態(tài)工作數(shù)組，這個(gè)數(shù)組有 rows行和 cols列。然后釋放為行指針分配的空間。 } 算法分析方法 ? 例：順序搜索算法 templateclass Type int seqSearch(Type *a, int n, Type k) { for(int i=0。 i n。 // c7 n1 } } ? 在最好情況下， ti=1, for 1 ? i n。 ? } ????????01)1(00)(nnTnnTnnT ?)(
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1