這節(jié)呢缅叠，主要說下，簡單的時間復(fù)雜度和時間復(fù)雜度怎么一眼就看出虏冻。
下一接會具體說明最好肤粱，最壞，分擔復(fù)雜度厨相。
一领曼、時間復(fù)雜度
例子：
1 private int test() {
2 int count = 0;
3 for (int i = 0; i < 10; i++){
4 count +=i;
5 }
6 return count;
7 }
忽略CPU 等其他因素的時間，大概估算下蛮穿。
假設(shè)：第2句代碼耗時1個單位cost_time庶骄，3-4行執(zhí)行了n次，耗時為2n個cost_time,
那么整體耗時多少呢践磅？
耗時： totlaTime = cost_time + 2n*cost_time = (2n+1)cost_time
可以看出來单刁，所有代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比。
所以就可以大概可以總結(jié)為：T(n) = O(n)
簡單的分析就是府适，分析時間復(fù)雜度時羔飞，忽略其他一些常量參數(shù)，因為在大數(shù)量級面前檐春，常量數(shù)據(jù)并不影響最后的結(jié)果逻淌，可以簡單的認為對于單層循環(huán)而言，時間復(fù)雜度為O(n),同理2層循環(huán)便是O(n^2),其他同理.
那么對于一段代碼具有單層循環(huán)和多層循環(huán)時間復(fù)雜度是多少呢疟暖，這里呢卡儒，按照最大的時間復(fù)雜度算就對了。
比如
private int test() {
int count = 0;
int count1 = 0;
for (int i = 0; i < 10; i++){
count +=i;
}
for (int i = 0 ;i <10;i++){
for (int j =0;j < 10 ; j ++){
count1 += j * i;
}
}
return count;
}
那么這個的時間復(fù)雜度就是： O(n^2)
常見的時間復(fù)雜度：
O(1)（常數(shù)階）俐巴、O(logn)（對數(shù)階）骨望、O(n)（線性階）、O(nlogn)（線性對數(shù)階）欣舵、O(n^2)（平方階）擎鸠、O(n^3)（立方階）
注意：
1.O(1) 并不是只有一行代碼，時間復(fù)雜度就是O(1),O(1) 只是常量級時間復(fù)雜度的一種表示方法,比如下面代碼是2行邻遏，時間復(fù)雜度也是O(1)糠亩。只要代碼的執(zhí)行時間不隨 n 的增大而增長，這樣代碼的時間復(fù)雜度我們都記作 O(1)准验。
int i = 3赎线；
int j = 99;
- 常見的O(logn)（對數(shù)階） 是怎么樣的形式呢？
int i =1;
while(i < n ){
i = i * 3 ;
}
從代碼中可以看出糊饱，變量 i 的值從 1 開始取垂寥，每循環(huán)一次就乘以 3。當大于 n 時，循環(huán)結(jié)束滞项。
回憶高中時的內(nèi)容狭归，是不是就是一個等比數(shù)列：3 9 27 71..... k => 3^0 3^1 3^2 3^3 ...... 3^x,
3^x = n => n = log3n 忽略常數(shù)，可以得出 logn
二文判、空間復(fù)雜度
空間復(fù)雜度指的是除特定空間外过椎，重新申請開辟的空間，以代碼為例
private int[] test(int n){
int[] a = new int[n];
for (int i =0; i <n; ++i) {
a[i] = i * i;
}
return a;
}
考慮空間復(fù)雜度時還是忽略一些常量數(shù)據(jù)戏仓，比如可以看到申請一個大小為n的數(shù)據(jù)空間疚宇，和一個常量的空間i,忽略常量，那么只剩n個內(nèi)存空間赏殃，那么可以大概說明空間復(fù)雜度為O(n),用算法舉例更具說服力敷待。
映射上節(jié)的純文字敘述：
復(fù)雜度分析方法
- 單段代碼看高頻：比如循環(huán)。
- 多段代碼取最大：比如一段代碼中有單循環(huán)和多重循環(huán)仁热，那么取多重循環(huán)的復(fù)雜度榜揖。
- 嵌套代碼求乘積：比如遞歸、多重循環(huán)等抗蠢。
- 多個規(guī)模求加法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù)举哟，那么這時就取二者復(fù)雜度相加。
第三節(jié)傳送門：http://www.reibang.com/p/0314afcde9b0
