1 時間復雜度概述
- 當一個程序產(chǎn)生的時候肋殴，就自然而然產(chǎn)生了執(zhí)行時間囤锉，我們不可能每次都去一個一個運行進行比較。于是一種省時省力的方法產(chǎn)生了护锤，這就是時間復雜度的來源嚼锄。總的來說：
時間復雜度簡化了我們的比較方法蔽豺。
2 時間復雜度計算
- 時間復雜度與執(zhí)行次數(shù)有關。于是流程為：
1.找出所有語句的頻度并組成執(zhí)行次數(shù)T(n)
2.T(n)的數(shù)量級,忽略常量拧粪、低次冪和最高次冪的系數(shù),f(n)=T(n)的數(shù)量級
3.T(n)=O(f(n))
舉例：
int num1, num2;
for(int i=0; i<n; i++){
num1 += 1;
for(int j=1; j<=n; j*=2){
num2 += num1;
}
}
1.語句int num1, num2;的頻度為1修陡；
語句i=0;的頻度為1沧侥；
語句i<n; i++; num1+=1; j=1; 的頻度為n；
語句j<=n; j=2; num2+=num1;的頻度為n*log2(n)*魄鸦；
(為什么會出現(xiàn)log2(n)呢宴杀？是因為循環(huán)x次，j=2^x ,當j=n時停止循環(huán)拾因，就是2^x=n則有l(wèi)og2(n)=x時停止 ,即循環(huán)次數(shù)為log2(n)旺罢。)
**T(n) = 2 + 4n + 3n*log2n
2.忽略掉T(n)中的常量、低次冪和最高次冪的系數(shù)绢记。
f(n) = n*logn
3.代入公式
T(n) =O(f(n))= O(n*logn)
3.時間復雜度比較
- 常數(shù)階O(1), 對數(shù)階O(logn), 線性階O(n), 線性對數(shù)階O(nlogn), 平方階O(n^2)扁达， 立方階O(n^3),...， k次方階O(n^k), 指數(shù)階O(2^n) 蠢熄。
Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)和Ο(n!)
一些大小需要根據(jù)問題的規(guī)模n來進行判斷跪解。
- Ο(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)。
- O(logn)签孔、Ο(n)叉讥、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間饥追。
- Ο(2n)和Ο(n!)稱為指數(shù)時間图仓。(它們的大小和n有關。)
