數據結構題集答案0001-資料下載頁
2025-06-24 00:44本頁面
【正文】 .+(1+2+3+...+n)= = = (6) n (7) 向下取整 (8) 1100 假設n為2的乘冪，并且n2，試求下列算法的時間復雜度及變量count的值（以n的函數形式表示）。int Time(int n) { count = 0。 x=2。 while(xn/2) { x *= 2。 count++。 }return count。 }解：count= 已知有實現(xiàn)同一功能的兩個算法，其時間復雜度分別為和，假設現(xiàn)實計算機可連續(xù)運算的時間為秒（100多天），又每秒可執(zhí)行基本操作（根據這些操作來估算算法時間復雜度）次。試問在此條件下，這兩個算法可解問題的規(guī)模（即n值的范圍）各為多少？哪個算法更適宜？請說明理由。解： n=40 n=16 則對于同樣的循環(huán)次數n，在這個規(guī)模下，第二種算法所花費的代價要大得多。故在這個規(guī)模下，第一種算法更適宜。 設有以下三個函數： ，請判斷以下斷言正確與否：(1) f(n)是O(g(n))(2) h(n)是O(f(n))(3) g(n)是O(h(n))(4) h(n)是O()(5) h(n)是O(nlogn)解：(1)對 (2)錯 (3)錯 (4)對 (5)錯 試設定若干n值，比較兩函數和的增長趨勢，并確定n在什么范圍內，函數的值大于的值。解：的增長趨勢快。但在n較小的時候，的值較大。 當n438時， 判斷下列各對函數和，當時，哪個函數增長更快？(1) ，(2) ，(3) ，(4) ，解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 試用數學歸納法證明：(1) (2)
環(huán)評公示相關推薦
鄂ICP備17016276號-1