數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案總結(jié)-文庫(kù)吧
2025-06-08 20:48 本頁(yè)面
【正文】 k=0。while(in){ k=k+10*i。i++。}分析：i=1。 //1k=0。 //1 while(in) //n{ k=k+10*i。 //n1i++。 //n1}由以上列出的各語句的頻度，可得該程序段的時(shí)間消耗：T(n)=1+1+n+(n1)+(n1)=3n可表示為T(n)=O(n)(3) i=1。 j=0。while(i+j=n){if (ij) j++。else i++。}分析：通過分析以上程序段，可將i+j看成一個(gè)控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要時(shí)間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時(shí)間為：T(n)=O(n) 按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100, (3/2)n，(2/3)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 答：常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列,依次為:常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。先將題中的函數(shù)分成如下幾類：常數(shù)階：2100對(duì)數(shù)階：lgnK次方階：、n(3/2)指數(shù)階 (按指數(shù)由小到大排)：nlgn、(3/2)n、2n、 n!、 nn注意：(2/3)^n由于底數(shù)小于1，所以是一個(gè)遞減函數(shù)，其數(shù)量級(jí)應(yīng)小于常數(shù)階。根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：(2/3)n 2100 lgn n(3/2) nlgn (3/2)n 2n n! nn 第二章第2章 作業(yè)：，, 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常有以下幾方面的考慮：。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1