基本的計(jì)算步驟
時(shí)間復(fù)雜度的定義
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T（n）表示，若有某個(gè)輔助函數(shù)f（n），使得當(dāng)n趨近于無窮大時(shí)，T（n）/f（n）的極限值為不等于零的常數(shù)，則稱f（n）是T（n）的同數(shù)量級(jí)函數(shù)。記作T（n）=O（f（n）），稱O（f（n））為算法的漸進(jìn)時(shí)間復(fù)雜度（O是數(shù)量級(jí)的符號(hào) ），簡(jiǎn)稱時(shí)間復(fù)雜度。托福答案
根據(jù)定義，可以歸納出基本的計(jì)算步驟
1. 計(jì)算出基本操作的執(zhí)行次數(shù)T（n）
基本操作即算法中的每條語句（以；號(hào)作為分割），語句的執(zhí)行次數(shù)也叫做語句的頻度。在做算法分析時(shí)，一般默認(rèn)為考慮最壞的情況。
2. 計(jì)算出T（n）的數(shù)量級(jí)
求T（n）的數(shù)量級(jí)，只要將T（n）進(jìn)行如下一些操作：
忽略常量、低次冪和最高次冪的系數(shù)
令f（n）=T（n）的數(shù)量級(jí)。
3. 用大O來表示時(shí)間復(fù)雜度
當(dāng)n趨近于無窮大時(shí)，如果lim（T（n）/f（n））的值為不等于0的常數(shù)，則稱f（n）是T（n）的同數(shù)量級(jí)函數(shù)。記作T（n）=O（f（n））。
一個(gè)示例：
（1） int num1, num2;
（2） for（int i=0; i<n; i++）{
（3） num1 += 1;
（4） for（int j=1; j<=n; j*=2）{
（5） num2 += num1;
（6） }
（7） }
分析：
1.
語句int num1, num2;的頻度為1;
語句i=0;的頻度為1;
語句i<n; i++; num1+=1; j=1; 的頻度為n;
語句j<=n; j*=2; num2+=num1;的頻度為n*log2n;
T（n） = 2 + 4n + 3n*log2n
2.
忽略掉T（n）中的常量、低次冪和最高次冪的系數(shù)
f（n） = n*log2n
3.
lim（T（n）/f（n）） = （2+4n+3n*log2n） / （n*log2n）
= 2*（1/n）*（1/log2n） + 4*（1/log2n） + 3
當(dāng)n趨向于無窮大，1/n趨向于0,1/log2n趨向于0
所以極限等于3.
T（n） = O（n*log2n）
簡(jiǎn)化的計(jì)算步驟
再來分析一下，可以看出，決定算法復(fù)雜度的是執(zhí)行次數(shù)最多的語句，這里是num2 += num1,一般也是最內(nèi)循環(huán)的語句。
并且，通常將求解極限是否為常量也省略掉？
于是，以上步驟可以簡(jiǎn)化為：
1. 找到執(zhí)行次數(shù)最多的語句
2. 計(jì)算語句執(zhí)行次數(shù)的數(shù)量級(jí)
3. 用大O來表示結(jié)果
繼續(xù)以上述算法為例，進(jìn)行分析：
1.
執(zhí)行次數(shù)最多的語句為num2 += num1
2.
T（n） = n*log2n
f（n） = n*log2n
3.
// lim（T（n）/f（n）） = 1
T（n） = O（n*log2n）
--------------------------------------------------------------------------------

一些補(bǔ)充說明
最壞時(shí)間復(fù)雜度
算法的時(shí)間復(fù)雜度不僅與語句頻度有關(guān)，還與問題規(guī)模及輸入實(shí)例中各元素的取值有關(guān)。一般不特別說明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。
求數(shù)量級(jí)
即求對(duì)數(shù)值（log），默認(rèn)底數(shù)為10,簡(jiǎn)單來說就是"一個(gè)數(shù)用標(biāo)準(zhǔn)科學(xué)計(jì)數(shù)法表示后，10的指數(shù)".例如，5000=5x10 3 （log5000=3） ,數(shù)量級(jí)為3.另外，一個(gè)未知數(shù)的數(shù)量級(jí)為其最接近的數(shù)量級(jí)，即最大可能的數(shù)量級(jí)。
求極限的技巧
要利用好1/n.當(dāng)n趨于無窮大時(shí)，1/n趨向于0
--------------------------------------------------------------------------------
一些規(guī)則（引自：時(shí)間復(fù)雜度計(jì)算 ）
1） 加法規(guī)則
T（n,m） = T1（n） + T2（n） = O （max （ f（n）， g（m） ）
2） 乘法規(guī)則
T（n,m） = T1（n） * T2（m） = O （f（n） * g（m））
3） 一個(gè)特例（問題規(guī)模為常量的時(shí)間復(fù)雜度）
在大O表示法里面有一個(gè)特例，如果T1（n） = O（c）， c是一個(gè)與n無關(guān)的任意常數(shù)，T2（n） = O （ f（n） ） 則有
T（n） = T1（n） * T2（n） = O （ c*f（n） ） = O（ f（n） ）
也就是說，在大O表示法中，任何非0正常數(shù)都屬于同一數(shù)量級(jí)，記為O（1）。
4） 一個(gè)經(jīng)驗(yàn)規(guī)則
復(fù)雜度與時(shí)間效率的關(guān)系：
c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! （c是一個(gè)常量）
|--------------------------|--------------------------|-------------|
較好 一般 較差
其中c是一個(gè)常量，如果一個(gè)算法的復(fù)雜度為c 、 log2n 、n 、 n*log2n,那么這個(gè)算法時(shí)間效率比較高 ,如果是 2n , 3n ,n!,那么稍微大一些的n就會(huì)令這個(gè)算法不能動(dòng)了，居于中間的幾個(gè)則差強(qiáng)人意。
--------------------------------------------------------------------------------------------------
復(fù)雜情況的分析
以上都是對(duì)于單個(gè)嵌套循環(huán)的情況進(jìn)行分析，但實(shí)際上還可能有其他的情況，下面將例舉說明。雅思答案
1.并列循環(huán)的復(fù)雜度分析
將各個(gè)嵌套循環(huán)的時(shí)間復(fù)雜度相加。
例如：
for （i=1; i<=n; i++）
x++;
for （i=1; i<=n; i++）
for （j=1; j<=n; j++）
x++;
解：
第一個(gè)for循環(huán)
T（n） = n
f（n） = n
時(shí)間復(fù)雜度為Ο（n）
第二個(gè)for循環(huán)
T（n） = n2
f（n） = n2
時(shí)間復(fù)雜度為Ο（n2）
整個(gè)算法的時(shí)間復(fù)雜度為Ο（n+n2） = Ο（n2）。
2.函數(shù)調(diào)用的復(fù)雜度分析
例如：
public void printsum（int count）{
int sum = 1;
for（int i= 0; i<n; i++）{
sum += i;
}
System.out.print（sum）；
}
分析：
記住，只有可運(yùn)行的語句才會(huì)增加時(shí)間復(fù)雜度，因此，上面方法里的內(nèi)容除了循環(huán)之外，其余的可運(yùn)行語句的復(fù)雜度都是O（1）。
所以printsum的時(shí)間復(fù)雜度 = for的O（n）+O（1） = 忽略常量 = O（n）
*這里其實(shí)可以運(yùn)用公式 num = n*（n+1）/2,對(duì)算法進(jìn)行優(yōu)化，改為：
public void printsum（int count）{
int sum = 1;
sum = count * （count+1）/2;
System.out.print（sum）；
}
這樣算法的時(shí)間復(fù)雜度將由原來的O（n）降為O（1），大大地提高了算法的性能。
3.混合情況（多個(gè)方法調(diào)用與循環(huán)）的復(fù)雜度分析
例如：
public void suixiangMethod（int n）{
printsum（n）；//1.1
for（int i= 0; i<n; i++）{
printsum（n）； //1.2
}
for（int i= 0; i<n; i++）{
for（int k=0; k
System.out.print（i,k）； //1.3
}
}
suixiangMethod 方法的時(shí)間復(fù)雜度需要計(jì)算方法體的各個(gè)成員的復(fù)雜度。
也就是1.1+1.2+1.3 = O（1）+O（n）+O（n2） ----> 忽略常數(shù) 和 非主要項(xiàng) == O（n2）
--------------------------------------------------------------------------------------------------
更多的例子
O（1）
交換i和j的內(nèi)容
temp=i;
i=j;
j=temp;
以上三條單個(gè)語句的頻度為1,該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T（n）=O（1）。如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語句，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O（1）。托福答案
O（n2）
sum=0; /* 執(zhí)行次數(shù)1 */
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
sum++; /* 執(zhí)行次數(shù)n2 */
解：T（n） = 1 + n2 = O（n2）
for （i=1;i<n;i++）
{
y=y+1; ①
for （j=0;j<=（2*n）；j++）
x++; ②
}
解： 語句1的頻度是n-1
語句2的頻度是（n-1）*（2n+1） = 2n2-n-1
T（n） = 2n2-n-1+（n-1） = 2n2-2
f（n） = n2
lim（T（n）/f（n）） = 2 + 2*（1/n2） = 2
T（n） = O（n2）。
O（n）
a=0;
b=1; ①
for （i=1;i<=n;i++） ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解： 語句1的頻度：2,
語句2的頻度：n,
語句3的頻度：n,
語句4的頻度：n,
語句5的頻度：n,
T（n） = 2+4n
f（n） = n
lim（T（n）/f（n）） = 2*（1/n） + 4 = 4
T（n） = O（n）。
O（log2n）
i=1; ①
while （i<=n）
i=i*2; ②

解： 語句1的頻度是1,
設(shè)語句2的頻度是t, 則：nt<=n; t<=log2n
考慮最壞情況，取最大值t=log2n,
T（n） = 1 + log2n
f（n） = log2n
lim（T（n）/f（n）） = 1/log2n + 1 = 1
T（n） = O（log2n）
O（n3）
for（i=0;i<n;i++）
{
for（j=0;j<i;j++）
{
for（k=0;k<j;k++）
x=x+2;
}
}
解：當(dāng)i=m, j=k的時(shí)候，內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí)， j 可以取 0,1,…，m-1 , 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+…+m-1=（m-1）m/2次所以，i從0取到n, 則循環(huán)共進(jìn)行了： 0+（1-1）*1/2+…+（n-1）n/2=n（n+1）（n-1）/2次
T（n） = n（n+1）（n-1）/2 = （n3-n）/2
f（n） = n3
所以時(shí)間復(fù)雜度為O（n3）。