時間復(fù)雜度的定義
? ? 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)蹈垢，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)袖裕，則稱f(n)是T(n)的同數(shù)量級函數(shù)曹抬。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時間復(fù)雜度(O是數(shù)量級的符號 )急鳄，簡稱時間復(fù)雜度谤民。
根據(jù)定義堰酿，可以歸納出基本的計算步驟
1. 計算出基本操作的執(zhí)行次數(shù)T(n)
? ? 基本操作即算法中的每條語句（以;號作為分割），語句的執(zhí)行次數(shù)也叫做語句的頻度张足。在做算法分析時触创，一般默認(rèn)為考慮最壞的情況。
2. 計算出T(n)的數(shù)量級
? ? 求T(n)的數(shù)量級为牍，只要將T(n)進(jìn)行如下一些操作：
? ? 忽略常量哼绑、低次冪和最高次冪的系數(shù)
? ? 令f(n)=T(n)的數(shù)量級。
3. 用大O來表示時間復(fù)雜度
? ? 當(dāng)n趨近于無窮大時吵聪，如果lim(T(n)/f(n))的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)兼雄。記作T(n)=O(f(n))吟逝。
一個示例：
(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)
簡化的計算步驟
再來分析一下庞呕，可以看出，決定算法復(fù)雜度的是執(zhí)行次數(shù)最多的語句程帕，這里是num2 += num1住练，一般也是最內(nèi)循環(huán)的語句。
并且愁拭，通常將求解極限是否為常量也省略掉讲逛？
于是，以上步驟可以簡化為：
1. 找到執(zhí)行次數(shù)最多的語句
2. 計算語句執(zhí)行次數(shù)的數(shù)量級
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ǔ)充說明
最壞時間復(fù)雜度
? ? 算法的時間復(fù)雜度不僅與語句頻度有關(guān)盏混，還與問題規(guī)模及輸入實例中各元素的取值有關(guān)。一般不特別說明惜论，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度许赃。這就保證了算法的運行時間不會比任何更長。
求數(shù)量級
即求對數(shù)值(log)馆类，默認(rèn)底數(shù)為10图焰，簡單來說就是“一個數(shù)用標(biāo)準(zhǔn)科學(xué)計數(shù)法表示后，10的指數(shù)”蹦掐。例如技羔，5000=5x10 3 (log5000=3) 僵闯，數(shù)量級為3。另外藤滥，一個未知數(shù)的數(shù)量級為其最接近的數(shù)量級鳖粟，即最大可能的數(shù)量級。
求極限的技巧
要利用好1/n拙绊。當(dāng)n趨于無窮大時向图，1/n趨向于0
--------------------------------------------------------------------------------
一些規(guī)則(引自：時間復(fù)雜度計算 )
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) 一個特例（問題規(guī)模為常量的時間復(fù)雜度）
在大O表示法里面有一個特例，如果T1(n) ＝ O(c)标沪， c是一個與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ù)量級檩赢，記為O(1)。
4) 一個經(jīng)驗規(guī)則
復(fù)雜度與時間效率的關(guān)系：
c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! （c是一個常量）
|--------------------------|--------------------------|-------------|
? ? ? ? ? 較好? ? ? ? ? ? ? ? ? ? 一般? ? ? ? ? ? ? 較差
其中c是一個常量违寞，如果一個算法的復(fù)雜度為c 贞瞒、 log2n 、n 趁曼、 n*log2n,那么這個算法時間效率比較高 军浆，如果是 2n , 3n ,n!,那么稍微大一些的n就會令這個算法不能動了，居于中間的幾個則差強(qiáng)人意挡闰。
--------------------------------------------------------------------------------------------------
復(fù)雜情況的分析
以上都是對于單個嵌套循環(huán)的情況進(jìn)行分析乒融，但實際上還可能有其他的情況，下面將例舉說明摄悯。
1.并列循環(huán)的復(fù)雜度分析
將各個嵌套循環(huán)的時間復(fù)雜度相加簇抵。
例如：
for (i=1; i<=n; i++)
? ? x++;
for (i=1; i<=n; i++)
? ? for (j=1; j<=n; j++)
? ? ? ? x++;
解：
第一個for循環(huán)
T(n) = n
f(n) = n
時間復(fù)雜度為Ο(n)
第二個for循環(huán)
T(n) = n2
f(n) = n2
時間復(fù)雜度為Ο(n2)
整個算法的時間復(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);
}
分析：
記住射众，只有可運行的語句才會增加時間復(fù)雜度碟摆，因此，上面方法里的內(nèi)容除了循環(huán)之外叨橱，其余的可運行語句的復(fù)雜度都是O(1)典蜕。
所以printsum的時間復(fù)雜度 = for的O(n)+O(1) = 忽略常量 = O(n)
*這里其實可以運用公式 num = n*(n+1)/2，對算法進(jìn)行優(yōu)化罗洗，改為：
public void printsum(int count){
? ? int sum = 1;
? ? sum = count * (count+1)/2;?
? ? System.out.print(sum);
}
這樣算法的時間復(fù)雜度將由原來的O(n)降為O(1)愉舔，大大地提高了算法的性能。
3.混合情況（多個方法調(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 方法的時間復(fù)雜度需要計算方法體的各個成員的復(fù)雜度伙菜。
也就是1.1+1.2+1.3 = O(1)+O(n)+O(n2) ----> 忽略常數(shù) 和 非主要項 == O(n2)
--------------------------------------------------------------------------------------------------
更多的例子
O(1)
交換i和j的內(nèi)容
temp=i;
i=j;
j=temp;? ? ? ? ? ? ? ? ? ?
以上三條單個語句的頻度為1轩缤，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)火的。如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長壶愤，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(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的時候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時, 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
所以時間復(fù)雜度為O(n3)。
