71304數(shù)據(jù)結(jié)構(gòu)-在線瀏覽
2024-12-03 09:39本頁面
【正文】 ? 三大特征 ? 信息隱藏、數(shù)據(jù)封裝、使用與實(shí)現(xiàn)分離 22 class Circle { // 對(duì)象 : 幾何圓 float r。 // 構(gòu)造函數(shù)，創(chuàng)建一個(gè)半徑為 r的對(duì)象實(shí)例 float Circumference( )。 // 返回該實(shí)例的面積 }。 ? 數(shù)據(jù)封裝：把數(shù)據(jù)和操作封裝在一起，從語義上更加完整。 23 抽象數(shù)據(jù)類型 ? 作業(yè)：二維向量的抽象數(shù)據(jù)類型 ? 數(shù)據(jù)類型 ? 操作：加、減、點(diǎn)乘、叉乘 24 算法定義 ? 是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。x=100。y=100。z=100。amp。amp。 } } } 算法定義 ? 算法舉例 ? 歐幾里德算法 ——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù) m和 n的最大公約數(shù) 27 輸入 : m,n 輸出 : m和 n的最大公約數(shù) r = m % n。 n = r。 } 輸出 n 算法性能分析與度量 ? 算法效率的評(píng)價(jià)方法： ? 事后統(tǒng)計(jì) ? 將算法實(shí)現(xiàn)，統(tǒng)計(jì)其時(shí)間和空間開銷 ? 事前分析 ? 對(duì)算法所消耗時(shí)間和空間資源的一種估算方法 ? 算法效率的分析 ? 時(shí)間復(fù)雜度 ? 空間復(fù)雜度 28 time (amp。 algorithm()。stop)。 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 29 算法的運(yùn)行時(shí)間 = 每條語句執(zhí)行時(shí)間之和 執(zhí)行次數(shù) 執(zhí)行一次的時(shí)間 例： for(i=0。i++) { for(j=0。j++) { c[i][j]=0。kn。 } } } 指令系統(tǒng)、代碼質(zhì)量有關(guān) 每條語句執(zhí)行次數(shù)之和 基本語句執(zhí)行次數(shù) 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? 算法的運(yùn)行時(shí)間可表示為基本語句執(zhí)行次數(shù)，它是問題規(guī)模的一個(gè)函數(shù) ? 稱這個(gè)函數(shù)的漸進(jìn)階為算法的時(shí)間復(fù)雜度 30 問題規(guī)模： n 基本語句： c[i][j]=0 c[i][j]=c[i][j]+a[i][k]*b[k][j] 時(shí)間復(fù)雜度 : O(n3) 例： for(i=0。i++) { for(j=0。j++) { c[i][j]=0。kn。 } } } 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? 大 O表示法：若存在兩個(gè)正的常數(shù) c和 n0，對(duì)于任意 n≥n0，都有 T(n) ≤ c f(n)，則稱 T(n)=O(f(n)) 31 n0 問題規(guī)模 n 執(zhí)行次數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1