基本概念和術(shù)語13抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)14算法和算-資料下載頁
2025-09-20 10:38本頁面
【導(dǎo)讀】空間復(fù)雜性分析。③數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)。表示和實(shí)現(xiàn)"的學(xué)科。例1求n個整數(shù)中的最大值。例2交叉路口的紅綠燈管理。例3煤氣管道的鋪設(shè)問題。例子中的數(shù)學(xué)模型正是數(shù)據(jù)結(jié)構(gòu)要討論的問題。問題涉及的對象：游泳池的長len寬wide，面積area；已知某級學(xué)生情況,要求分班按入學(xué)成績排列順序。常存在著一種最簡單的線性關(guān)系,該數(shù)學(xué)模型稱為線性模型。算機(jī)預(yù)先分析7至8個回合的著法。若設(shè)為7個回合，則有超過。1億億億個不同的變化，經(jīng)簡化后，仍有500億至600億個變化。平均5分鐘走一步。相當(dāng)于“記錄”,在計(jì)算機(jī)程序。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)之間的相互關(guān)系，政治、面貌，表中的記錄是按學(xué)生的學(xué)號順序排列的。同一邏輯結(jié)構(gòu)的丌同存儲結(jié)構(gòu)，冠以丌同的數(shù)據(jù)結(jié)構(gòu)名。程序的正確性容易保證。軟件設(shè)計(jì)是對數(shù)據(jù)抽象、過程抽象和控制抽象。
【正文】 語句頻度 ：語句重復(fù)執(zhí)行的次數(shù) 第 1章 緒論 算法與算法分析 ① 程序運(yùn)行時輸入數(shù)據(jù)的總量 。 ② 對源程序編譯所需的時間 。 ③ 計(jì)算機(jī)執(zhí)行每條指令所需的時間 。 ④ 程序中指令重復(fù)執(zhí)行的次數(shù)。 ?所有算法均以函數(shù)形式給出 , 算法的輸入數(shù)據(jù)來自參數(shù)表； ?參數(shù)表的參數(shù)在算法之前均進(jìn)行類型說明； ?有關(guān)結(jié)點(diǎn)結(jié)構(gòu)的類型定義 ,以及全局變量的說明等均在算法之前進(jìn)行說明 ?描述算法的書寫規(guī)則 第 1章 緒論 算法與算法分析 ? 評價算法標(biāo)準(zhǔn) ?本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時間的度量。 ?O(n3) 稱為矩陣相乘算法時間復(fù)雜度； ?O(n3)表示矩陣相乘算法執(zhí)行時間不 n3成正比 , 即 O（ n3）不 n3 同一數(shù)量級； n 階矩陣相乘的算法 For ( i = 1。 i=n。 i++ ) For (j = 1。 j=n。 j++ ) { c[ i ][ j ] = 0 。 For (k = 1。 k= n。 k++ ) c[ i ][ j ] += a[ i ][ k ] * b[ k ] [ j ] } 乘法 加法 執(zhí)行次數(shù)均為 n3 例 第 1章 緒論 算法與算法分析 說明： 有些算法，基本操作執(zhí)行次數(shù)不問題的輸入數(shù)據(jù)有關(guān)，這時可考慮 ① 算法平均時間復(fù)雜度 ② 算法在最壞情況下的時間復(fù)雜度 ?算法的時間復(fù)雜度 T(n) 第 1章 緒論 算法與算法分析 一般來說，設(shè)算法中基本操作的執(zhí)行次數(shù)是問題規(guī)模 n的某個函數(shù) f(n)， 算法的時間復(fù)雜度 記作： T(n) = O(f(n)) 它表示隨問題規(guī)模 n的增大，算法執(zhí)行時間的增長率不 f(n) 的增長率相同。 define N 100 void scheme() { int i, j, k, count, money。 for (i = 0。 i=N。 i++ ) for (j = 0。 j=N。 j++ ) for (k=0。 k=N。 k++) { count=i+j+k。 money=3*i+2*j+*k。 if ( count==N amp。amp。 money==N) printf (“%d, %d, %d \n%”, i, j, k) 。 } } 算法的時間復(fù)雜度為 O (n3) 100元買 100支筆 , 其中鋼筆 3元 /支 , 圓珠筆 2元 /支 , 鉛筆 /支，各種組合方案的算法如下，計(jì)算時間復(fù)雜度。 例 第 1章 緒論 算法與算法分析 本章小結(jié) ?數(shù)據(jù)結(jié)構(gòu)和算法等基本概念； ?數(shù)據(jù)的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)和非線性結(jié)構(gòu)； ?數(shù)據(jù)的存儲結(jié)構(gòu)可以用以下存儲方法； ① 順序存儲 ② 鏈?zhǔn)酱鎯? ③ 索引存儲 ④ 散列存儲 ?抽象數(shù)據(jù)類型 ?算法的特性 ?算法的復(fù)雜度分析 第 1章 緒論 思考題： 操作系統(tǒng)是否是算法？ 第 1章 緒論
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1