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