結(jié)構(gòu)的抽象層次用c+描述面向?qū)ο蟪绦蛩惴ǘx模板性能分析與度(文件)
【正文】 特點(diǎn)。 i n1。 i n1。 j++ ) if ( a[j] a[k] ) k = j。 } } 模板 (template) 定義 適合 多種數(shù)據(jù)類型 的類定義或算法，在特定環(huán)境下通過(guò)簡(jiǎn)單地代換，變成 針對(duì)具體某種數(shù)據(jù)類型 的類定義或算法 用模板定義用于排序的數(shù)據(jù)表類 include template class Type class dataList { private: Type *Element。 public: dataList (int size = 10) : ArraySize (size), Element (new Type [Size]) { } dataList ( ) {delete [ ] Element。 outStream, datalistTypeamp。 inStream, datalistTypeamp。 Element [m2] = temp。 } template class Type ostreamamp。 i 。 return OutStream。 Instream 。 i++) { cout “元素 ” i “:” 。 i 0。 int main ( ) { dataList int TestList (SIZE)。 cout TestList endl。amp。 } 插裝 time( ) 的計(jì)時(shí)程序 double start, stop。 time (amp。 算法的事前估計(jì) ? 空間復(fù)雜度 ? 時(shí)間復(fù)雜度 空間復(fù)雜度度量 ? 存儲(chǔ)空間的固定部分 程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分 (如數(shù)組元素、結(jié)構(gòu)成分、對(duì)象的數(shù)據(jù)成員等 )變量所占空間 ? 可變部分 尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過(guò) new和 delete命令動(dòng)態(tài)使用空間 時(shí)間復(fù)雜度度量 ? 編譯時(shí)間 ? 運(yùn)行時(shí)間 ? 程序步 ?語(yǔ)法上或語(yǔ)義上有意義的一段指令 序列 ?執(zhí)行時(shí)間與實(shí)例特性無(wú)關(guān) ?例如： 聲明語(yǔ)句 ：程序步數(shù)為 0。 i++ ) s += a[i]。 //count 統(tǒng)計(jì)執(zhí)行語(yǔ)句條數(shù) for ( int i = 0。 count++。 } 執(zhí)行結(jié)束的程序步數(shù) count = 2*n+3 程序的簡(jiǎn)化形式 void sum ( float a[ ], int n ) { for ( int i = 0。 } 注意 ： 一個(gè)語(yǔ)句本身的程序步數(shù)可能不等于該語(yǔ)句一次執(zhí)行所具有的程序步數(shù)。 i++ ) 1 n+1 n+1 s += a[ i] 。 i m。 j++ ) sum[i] += x[i][j]。 } 漸進(jìn)時(shí)間復(fù)雜度為 O(max (m*n, m)) template class Type //起泡排序 void dataListType :: bubbleSort ( ) { //對(duì)表逐趟比較 , ArraySize 是表當(dāng)前長(zhǎng)度 int i = 1。 exchange ) { BubbleExchange ( i, exchange )。 //假定元素未交換 for ( int j = ArraySize1。 //做“發(fā)生交換”標(biāo)志 } } 漸進(jìn)時(shí)間復(fù)雜度 O(f (n)*g (n)) = O(n2) ??????11 21ni)n(ni)(n?BubblrSort n1趟 BubbleExchange ( ) ni次比較 。 j) if ( Element[j1] Element[j] ) { Swap ( j 1, j )。 } //一趟比較 } template class Type void dataListType:: BubbleExchange(int i, int amp。 //當(dāng) exchange 為 0 則停止排序 while ( i ArraySize amp。 i m。 //數(shù)據(jù)累加
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1