北京師大教育技術(shù)考研數(shù)據(jù)結(jié)構(gòu)09答案(已修改)
2024-11-26 17:35 本頁面
【正文】 1 北京師范大學(xué) 2020年招收碩士學(xué)位研究生入學(xué)考試試題 答案 一、 時間復(fù)雜度分析 冒泡排序的時間復(fù)雜度為： T(n) = O(n^2) 快速排序的時間復(fù)雜度為： T(n) = O(n*log n) （前面的報(bào)告中已經(jīng)有分析說明） 堆 排序的時間復(fù)雜度為 ： T(n) = O(n*log n) （ 在最壞的情況下） 堆排序的運(yùn)行時間主要是耗費(fèi)在建立初始堆和調(diào)整建立新堆的反復(fù)篩選上面，在建立初始堆的時候，需要的時間是0(n)。因?yàn)樵诮ǔ跏级训臅r候，調(diào)用 Heapify() n/2次，有 Heapify()所需要的時間可知道，當(dāng) i在 n/2 的到 n/4+1 的范圍內(nèi)時，每次調(diào)用耗費(fèi)時間為 C， C 為一常數(shù)，當(dāng) i 在 n/4 到 n /8+1的范圍內(nèi)時，耗費(fèi)的時間為 2C，………。所以 C(n/4+2*n/8+3*n/16+…… ..)=O(n) 在調(diào)整堆的時候，調(diào)用 Heapify 共 n1 次，每次調(diào)用所需要的時間為 O(n)的時間，所以整個算法在最壞的情況下只需要： T(n) = O(n*log n) 的時間。 運(yùn)行結(jié)果和分析 1）當(dāng)數(shù)組的規(guī)模都為 10000 個元素 的時候： 冒泡排序所需的時間是： ；快速排序和堆排序基本上不需要時
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1