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