0x01 時間復(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ù)雜度。
0x02 時間復(fù)雜度的計算步驟
計算出基本操作的執(zhí)行次數(shù)T(n)
??基本操作即算法中的每條語句（以;號作為分割）忱辅，語句的執(zhí)行次數(shù)也叫做語句的頻度七蜘。在做算法分析時，一般默認(rèn)為考慮最壞的情況墙懂。計算出T(n)的數(shù)量級
??求T(n)的數(shù)量級橡卤，只要將T(n)進(jìn)行如下一些操作：忽略常量、低次冪和最高次冪的系數(shù)损搬。令f(n)=T(n)的數(shù)量級碧库。用大O來表示時間復(fù)雜度
??當(dāng)n趨近于無窮大時柜与，如果lim(T(n)/f(n))的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)嵌灰。記作T(n)=O(f(n))弄匕。
總結(jié)一下就是
- 找到執(zhí)行次數(shù)最多的語句
- 計算語句執(zhí)行次數(shù)的數(shù)量級
- 用大O來表示結(jié)果
0x03 例子
- O(1)
int i = 0,j = 0,temp = 0;
temp = i;
i = j;
j = temp;
這個是一個交換兩個變量值的例子，三個語句的頻度都是1沽瞭，該程序執(zhí)行時間是一個與問題規(guī)模n無關(guān)的迁匠，算法的時間復(fù)雜度為常數(shù)，所以T(n) = O(1)驹溃。
P.S 如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長城丧，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)豌鹤。此類算法的時間復(fù)雜度是O(1)亡哄。
- O(n)
int sum = 0;
for(int i = 0; i < n; i++){
sum = sum + i;
}
T(n) = 1 + n
上述代碼的時間復(fù)雜度就是for循環(huán)的O(n)
- O(logn)
int i= 1;
while(i<n){
i = i*2;
}
設(shè)i=i*2的頻度為t，則2^t <= n布疙，那么t <= log2n蚊惯。取最壞結(jié)果，當(dāng)t等于最大值log2n是T(n) = 1 + log2n灵临，所以時間復(fù)雜度為O(log2n)
- O(n^2)
int sum = 0;
for(int i = 0;i <= n;i++){
for(int j = 0;j <= n; j++){
sum++;
}
}
時間復(fù)雜度為O(n^2)
0x04 常用排序算法的時間復(fù)雜度
0x05 參考文獻(xiàn)
http://www.reibang.com/p/99bac69fdd97
http://univasity.iteye.com/blog/1164707
http://blog.csdn.net/zolalad/article/details/11848739
