數(shù)據(jù)結(jié)構(gòu)與算法培訓(xùn)教案-wenkub.com
2025-04-14 01:46 本頁(yè)面
【正文】 并思考下列問(wèn)題。 （3）算法的空間效率度量方法（空間復(fù)雜度）（約5分鐘）空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的度量，記作：S(n) = O(g(n))表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。 } j n。 //從a[i]查到a[n1], 找最小整數(shù), 在a[k] int k = i。 舉例說(shuō)明時(shí)間復(fù)雜度的計(jì)算方法：例對(duì) n 個(gè)整數(shù)的序列進(jìn)行選擇排序。設(shè)解決一個(gè)問(wèn)題的規(guī)模為n ，基本操作被重復(fù)執(zhí)行的次數(shù)是n的一個(gè)函數(shù) f（n），假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：} ++x的頻度為n2 j=n。 ++i) {++x。（a） {++x。一個(gè)特定算法“運(yùn)行工作量”大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。 效率與低存儲(chǔ)需求：主要指算法的執(zhí)行時(shí)間和所需的最大存儲(chǔ)空間，這兩方面主要和問(wèn)題的規(guī)模有關(guān)。– 輸出：有一個(gè)或多個(gè)輸出(處理結(jié)果)。 輸入：有0個(gè)或多個(gè)輸入– 可行性：算法中描述的操作應(yīng)能通過(guò)執(zhí)行有限次已經(jīng)實(shí)現(xiàn)的基本運(yùn)算實(shí)現(xiàn)– 確定性：每步定義都是確切、無(wú)歧義的– 有窮性：算法應(yīng)在執(zhí)行有窮步后結(jié)束,且每一步都在有窮時(shí)間內(nèi)完成–（2）算法的特性(要素) –167。 基本操作：〈基本操作的定義〉 抽象數(shù)據(jù)類型（約35分鐘）由數(shù)據(jù)類型定義引入抽象數(shù)據(jù)類型的定義。其他√教學(xué)目的及要求（分掌握、理解、了解三個(gè)層次）：了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。音像 相關(guān)軟件 其他□教學(xué)資源多媒體課件√ 練習(xí) 閱讀√ 實(shí)習(xí)或課程設(shè)計(jì)注：表中選項(xiàng)打“√”【第二次（2學(xué)時(shí)）】教學(xué)主題或章、節(jié)前面章節(jié)簡(jiǎn)要回顧、 算法及其分析授課類型理論課√ 重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)所涉及的基本概念、數(shù)據(jù)結(jié)構(gòu)的分類，數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、他們之間的關(guān)系。 習(xí)題練習(xí)。小結(jié)（約2分鐘）內(nèi)容回顧、重點(diǎn)、難點(diǎn)。綜合比較數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間的關(guān)系，并舉例說(shuō)明。舉例說(shuō)明：以復(fù)數(shù)為例，說(shuō)明復(fù)數(shù)類的數(shù)據(jù)結(jié)構(gòu)形式定義方式。引出數(shù)據(jù)元素之間的關(guān)系、數(shù)據(jù)結(jié)構(gòu)的定義。舉例說(shuō)明。舉例說(shuō)明。舉例說(shuō)明：（1）圖書檢索系統(tǒng)中所涉及到的數(shù)據(jù)之間的關(guān)系——線性關(guān)系（2）人家對(duì)弈問(wèn)題過(guò)程中所涉及到的棋盤與棋盤數(shù)據(jù)之間的關(guān)系——樹型結(jié)構(gòu)（3）十
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1