◆ （2）成立。
◆ （3）成立。
◆ （4）不成立。
1.5 設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100n^2和2^n,要使前者快于后者，n至少要多大?
◆ 15
◇ 最簡(jiǎn)單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我們就加個(gè)5，用15代入得前者為 22500，后者為32768，已經(jīng)比前者大但相差不多，那我們?cè)贉p個(gè)1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來就是n至少要是15.
1.6 設(shè)n為正整數(shù)，利用大"o"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。
(1) i=1; k=0
while(i
{ k=k+10*i;i++;
} ◆ t(n)=n-1
∴ t(n)=o(n)
◇ 這個(gè)函數(shù)是按線性階遞增的
(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i<> ◆ t(n)=n
∴ t(n)=o(n)
◇ 這也是線性階遞增的
(3) i=1; j=0;
while(i+j<=n)
{
if (i
else i++;
} ◆ t(n)=n/2
∴ t(n)=o(n)
◇ 雖然時(shí)間函數(shù)是n/2,但其數(shù)量級(jí)仍是按線性階遞增的。
(4) x=n; // n>1
while (x>=(y+1)*(y+1))
y++; ◆ t(n)=n 1/2
∴ t(n)=o(n 1/2 )
◇ 最壞的情況是y=0，那么循環(huán)的次數(shù)是n 1/2 次，這是一個(gè)按平方根階遞增的函數(shù)。
(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++; ◆ t(n)=o(1)
◇ 這個(gè)程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到 n 沒有? 沒。這段程序的運(yùn)行是和n無(wú)關(guān)的，就算它再循環(huán)一萬(wàn)年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。
1.7 算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?
◆ no,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們?cè)谟懻摃r(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。
1.8 按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：
2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)，√n
◇ 分析如下： 2^100 是常數(shù)階； (2/3)^n 和 (3/2)^n 是指數(shù)階,其中前者是隨n的增大而減小的； n^n 是指數(shù)方階； √n 是方根階, n! 就是n(n-1)(n-2)... 就相當(dāng)于n次方階； 2^n 是指數(shù)階， lgn 是對(duì)數(shù)階 , n^lgn 是對(duì)數(shù)方階, n^(3/2) 是 3/2 次方階。根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：
◆ (2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n
1.9 有時(shí)為了比較兩個(gè)同數(shù)量級(jí)算法的優(yōu)劣，須突出主項(xiàng)的常數(shù)因子，而將低次項(xiàng)用大"o"記號(hào)表示。例如，設(shè)t1(n)=1.39nlgn+100n+256= 1.39nlgn+o(n), t2(n)=2.0nlgn-2n=2.0lgn+o(n), 這兩個(gè)式子表示，當(dāng)n足夠大時(shí)t1(n)優(yōu)于t2(n)，因?yàn)榍罢叩某?shù)因子小于后者。請(qǐng)用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時(shí)，哪一個(gè)較優(yōu)，哪一個(gè)較劣?
函 數(shù) 大"o"表示 優(yōu)劣
(1) t1(n)=5n^2-3n+60lgn ◆ 5n^2+o(n) ◆ 較差
(2) t2(n)=3n^2+1000n+3lgn ◆ 3n^2+o(n) ◆ 其次
(3) t3(n)=8n^2+3lgn ◆ 8n^2+o(lgn) ◆ 最差
(4) t4(n)=1.5n^2+6000nlgn ◆ 1.5n^2+o(nlgn) ◆
◆ （3）成立。
◆ （4）不成立。
1.5 設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100n^2和2^n,要使前者快于后者，n至少要多大?
◆ 15
◇ 最簡(jiǎn)單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我們就加個(gè)5，用15代入得前者為 22500，后者為32768，已經(jīng)比前者大但相差不多，那我們?cè)贉p個(gè)1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來就是n至少要是15.
1.6 設(shè)n為正整數(shù)，利用大"o"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。
(1) i=1; k=0
while(i
{ k=k+10*i;i++;
} ◆ t(n)=n-1
∴ t(n)=o(n)
◇ 這個(gè)函數(shù)是按線性階遞增的
(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i<> ◆ t(n)=n
∴ t(n)=o(n)
◇ 這也是線性階遞增的
(3) i=1; j=0;
while(i+j<=n)
{
if (i
else i++;
} ◆ t(n)=n/2
∴ t(n)=o(n)
◇ 雖然時(shí)間函數(shù)是n/2,但其數(shù)量級(jí)仍是按線性階遞增的。
(4) x=n; // n>1
while (x>=(y+1)*(y+1))
y++; ◆ t(n)=n 1/2
∴ t(n)=o(n 1/2 )
◇ 最壞的情況是y=0，那么循環(huán)的次數(shù)是n 1/2 次，這是一個(gè)按平方根階遞增的函數(shù)。
(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++; ◆ t(n)=o(1)
◇ 這個(gè)程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到 n 沒有? 沒。這段程序的運(yùn)行是和n無(wú)關(guān)的，就算它再循環(huán)一萬(wàn)年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。
1.7 算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?
◆ no,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們?cè)谟懻摃r(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。
1.8 按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：
2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)，√n
◇ 分析如下： 2^100 是常數(shù)階； (2/3)^n 和 (3/2)^n 是指數(shù)階,其中前者是隨n的增大而減小的； n^n 是指數(shù)方階； √n 是方根階, n! 就是n(n-1)(n-2)... 就相當(dāng)于n次方階； 2^n 是指數(shù)階， lgn 是對(duì)數(shù)階 , n^lgn 是對(duì)數(shù)方階, n^(3/2) 是 3/2 次方階。根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：
◆ (2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n
1.9 有時(shí)為了比較兩個(gè)同數(shù)量級(jí)算法的優(yōu)劣，須突出主項(xiàng)的常數(shù)因子，而將低次項(xiàng)用大"o"記號(hào)表示。例如，設(shè)t1(n)=1.39nlgn+100n+256= 1.39nlgn+o(n), t2(n)=2.0nlgn-2n=2.0lgn+o(n), 這兩個(gè)式子表示，當(dāng)n足夠大時(shí)t1(n)優(yōu)于t2(n)，因?yàn)榍罢叩某?shù)因子小于后者。請(qǐng)用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時(shí)，哪一個(gè)較優(yōu)，哪一個(gè)較劣?
函 數(shù) 大"o"表示 優(yōu)劣
(1) t1(n)=5n^2-3n+60lgn ◆ 5n^2+o(n) ◆ 較差
(2) t2(n)=3n^2+1000n+3lgn ◆ 3n^2+o(n) ◆ 其次
(3) t3(n)=8n^2+3lgn ◆ 8n^2+o(lgn) ◆ 最差
(4) t4(n)=1.5n^2+6000nlgn ◆ 1.5n^2+o(nlgn) ◆