數(shù)據(jù)結(jié)構(gòu)與算法培訓(xùn)教案-資料下載頁(yè)
2025-04-17 01:46本頁(yè)面
【正文】 中T（n）叫算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度， O是Order（數(shù)量級(jí)）的首字母，意思是T（n）與f（n）只差一個(gè)常數(shù)倍。 舉例說(shuō)明時(shí)間復(fù)雜度的計(jì)算方法：例對(duì) n 個(gè)整數(shù)的序列進(jìn)行選擇排序。其中序列的“長(zhǎng)度” n 為問(wèn)題的規(guī)模。void selectSort ( int a[ ], int n ) {//對(duì)n個(gè)整數(shù)a[0],a[1],…,a[n1]按遞增順序排序 for ( int i = 0。 i n1。 i++ ) { int k = i。 //從a[i]查到a[n1], 找最小整數(shù), 在a[k] for ( int j = i+1。 j n。 j++ ) if ( a[j] a[k] ) k = j。 int temp = a[i]。 a[i] = a[k]。 a[k] = temp。 }} （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)率相同。算法的存儲(chǔ)量包括：– 輸入數(shù)據(jù)所占空間； – 程序本身所占空間； – 輔助變量所占空間 167。小結(jié)（約3分鐘）內(nèi)容回顧、重點(diǎn)、難點(diǎn)。第三部分 布置作業(yè)（約2分鐘）書(shū)面作業(yè)：閱讀教材程序段、分析其時(shí)間復(fù)雜度。并思考下列問(wèn)題。1 為什么要學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》？2 學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》什么內(nèi)容？3 如何學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》？重點(diǎn)和難點(diǎn)：重點(diǎn)：掌握時(shí)間復(fù)雜度的概念、會(huì)計(jì)算問(wèn)題的時(shí)間復(fù)雜度，了解空間復(fù)雜度。難點(diǎn)：抽象數(shù)據(jù)類(lèi)型概念的理解、問(wèn)題時(shí)間復(fù)雜度的計(jì)算。參考資料：《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏等編著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與習(xí)題詳解》張鳳琴等編，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言篇）習(xí)題與解析》李春葆編，清華大學(xué)出版社注意事項(xiàng)及心得： 抽象數(shù)據(jù)類(lèi)型要簡(jiǎn)略講，注意把握時(shí)間。注：表中選項(xiàng)打“√”9 /
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1