中南大學數(shù)據(jù)結構與算法-第1章緒論課后作業(yè)答案-資料下載頁
2025-07-23 23:26本頁面
【正文】 復雜度時，一般就是以最壞情況下的時間復雜度為準的。 按增長率由小至大的順序排列下列各函數(shù)： 2100, (3/2)n，(2/3)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 答： 常見的時間復雜度按數(shù)量級遞增排列,依次為:常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。先將題中的函數(shù)分成如下幾類：常數(shù)階：2100對數(shù)階：lgnK次方階：、n(3/2)指數(shù)階 (按指數(shù)由小到大排)：nlgn、(3/2)n、2n、 n!、 nn注意：(2/3)^n由于底數(shù)小于1，所以是一個遞減函數(shù)，其數(shù)量級應小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下：(2/3)n 2100 lgn n(3/2) nlgn (3/2)n 2n n! nn 有時為了比較兩個同數(shù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大O記號表示。例如，設T1(n)=+100n+256=+O(n), T2(n)==+O(n), 這兩個式子表示，當n足夠大時T1(n)優(yōu)于T2(n)，因為前者的常數(shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當n足夠大時，哪一個較優(yōu)，哪一個較劣? 函數(shù) 大O表示 優(yōu)劣(1) T1(n)=5n23n+60lgn 5n2+O(n) 較差(2) T2(n)=3n2+1000n+3lgn 3n2+O(n) 其次(3) T3(n)=8n2+3lgn 8n2+O(lgn) 最差(4) T4(n)=+6000nlgn +O(nlgn) 最優(yōu)
環(huán)評公示相關推薦
鄂ICP備17016276號-1