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