建站服務(wù)器
1、常見的算法的時(shí)間復(fù)雜度比較：
常見的算法時(shí)間復(fù)雜度由小到大依次為：
ο1)＜οlogn)＜οn)＜οnlogn)＜οn2)＜οn3)＜…＜ο2)＜οn!)
ο1)表示基本語(yǔ)句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來(lái)說，只要算法中不存在循環(huán)語(yǔ)句，其時(shí)間復(fù)雜度就是ο1)。οlogn)、οn)、οnlogn)、οn2)和οn3)稱為多項(xiàng)式時(shí)間，而ο2)和οn!)稱為指數(shù)時(shí)間。計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者是有效算法，把這類問題稱為p類問題，而把后者稱為np問題。
這只能基本的計(jì)算時(shí)間復(fù)雜度，具體的運(yùn)行還會(huì)與硬件有關(guān)。
2、計(jì)算時(shí)間復(fù)雜度的相關(guān)題目;
一、單項(xiàng)選擇題
1.一個(gè)算法應(yīng)該是（ ）。
a.程序 b.問題求解步驟的描述 c.要滿足五個(gè)基本特性 d. a和c
1. b
程序不一定滿足有窮性，如死循環(huán)、操作系統(tǒng)等，而算法必須有窮。算法代表了對(duì)問題求解步驟的描述，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。
2.某算法的時(shí)間復(fù)雜度為o(n2)，表明該算法的（ ）。
a.問題規(guī)模是n2 b.執(zhí)行時(shí)間等于n2
c.執(zhí)行時(shí)間與n2成正比 d.問題規(guī)模與n2成正比
2. c
時(shí)間復(fù)雜度為o(n2)，說明算法的執(zhí)行時(shí)間t(n)<=c * n2(c為比例常數(shù))，即t(n)=o(n2)，時(shí)間復(fù)雜度t(n)是問題規(guī)模n的函數(shù)，其問題規(guī)模仍然是n而不是n2。
3.以下算法的時(shí)間復(fù)雜度為（ ）。
void fun(int n) {
int i=l;
while(i<=n)
i=i*2;
}
a.o(n) b. o(n2) c. o(nlog2n) d. o(log2n)
3. d
基本運(yùn)算是i=i*2，設(shè)其執(zhí)行時(shí)間為t(n)，則2t(n)<=n，即t(n)<=log2n=o(log2n)。
4.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是（）。
x=2;
while(x<n/2)
x=2*x;
a.o(log2n) b. o(n) c. o(nlog2n) d. o(n2)
4. a
在程序中，執(zhí)行頻率最高的語(yǔ)句為“x=2*x”。設(shè)該語(yǔ)句共執(zhí)行了 t次，則2t 1=n/2，故t=log2(n/2)-1=log2n-2，得 t(n)=o(log2n)。
5.【2012年計(jì)算機(jī)聯(lián)考真題】
求整數(shù)n (n>=0)階乘的算法如下，其時(shí)間復(fù)雜度是（ ）。
int fact(int n){
if (n<=l) return 1;
return n*fact(n-1);
}
a.o(log2n) b. o(n) c. o(nlog2n) d. o(n2)
5. b
本題是求階乘n!的遞歸代碼，即n*(n-1)*…*1共執(zhí)行n次乘法操作，故t(n)=o(n)。
6.有以下算法，其時(shí)間復(fù)雜度為（ ）。
void fun (int n){
int i=0;
while(i*i*i<=n)
i ;
}
a. o(n) b. o(nlogn) c. d.
7.程序段
for(i=n-l;i>l;i–)
for(j=1;j<i;j )
if (a[j]>a[j l])
a[j]與 a[j 1]對(duì)換;
其中n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（ ）。
a.o(n) b. o(nlogn) c. o(n3) d. o(n2)
8.以下算法中加下劃線語(yǔ)句的執(zhí)行次數(shù)為（）。
int m=0, i, j;
for(i=l;i<=n;i )
for(j=1;j<=2 * i;j )
m ;
a. n(n 1) b. n c. n 1 d. n2