時(shí)間復(fù)雜度的意義
時(shí)間復(fù)雜度是對(duì)算法好壞衡量的一個(gè)標(biāo)準(zhǔn)。試想同樣一個(gè)功能a算法實(shí)現(xiàn)只要1000ms內(nèi)存只有5MB，而b算法需要2000ms甚至更多，內(nèi)存需要50MB甚至跟多
衡量代碼的好壞包括兩個(gè)非常重要的指標(biāo)：
- 運(yùn)行時(shí)間
- 占用空間
由于代碼的運(yùn)行環(huán)境和規(guī)模影響，絕對(duì)時(shí)間是無(wú)法猜測(cè)出來(lái)的但是可以根據(jù)代碼的執(zhí)行次數(shù)來(lái)預(yù)顧出時(shí)間
基本操作執(zhí)行次數(shù)
一： 例如有10斤大米，每2天吃1斤吁峻，那么吃掉10斤大米需要幾天
答案是 2x10 = 20天
如果大米的重量是N斤那么吃掉所有的大米就需要 2 x n = 2n 天
所以相對(duì)時(shí)間就是 T(n) = 2n
二： 例如有20斤大米，每3天吃掉剩余大米的一半第一天吃10斤，第二天吃5斤用含，第三天吃2.5斤橙困，那么需要多少天
答案是 3 x log20 = 3 x 4 + 1天 = 13天
如果大米的重量是N斤那么需要 3 x logn
相對(duì)時(shí)間就是 T(n) = 3logn
三：例如有5斤大米和一個(gè)雞腿，2天吃掉一個(gè)雞腿那么吃掉整個(gè)雞腿所需時(shí)間耕餐？
答案是：2天 因?yàn)橹皇钦f(shuō)雞腿跟大米沒(méi)有關(guān)系
如果大米重量是n凡傅，無(wú)論大米多重吃雞腿的實(shí)際仍然是2天
T(n) = 2
四：例如有10斤大米，吃掉第一個(gè)1斤需要1天肠缔，第二個(gè)1斤需要兩天 第三個(gè)1斤需要三天... 那么吃掉所有大米時(shí)間是多少呢夏跷？
答案是： (1+2+3+4...+7+8+9+10) = 55
如果大米重量是N那么時(shí)間為 (1+2+3...+n-2+n-1+n) = (1 + n) * (n*0.5) = 0.5 * n^2 + 0.5 * n
T(n) = 0.5^2 + 0.5n
這一思想同樣適用于對(duì)程序基本操作執(zhí)行次數(shù)的統(tǒng)計(jì)
一： T(n) = 2n
void eat1(int n){
for(int i=0; i<n; i++){;
System.out.println("等待一天");
System.out.println("等待一天");
System.out.println("吃一斤米");
}
二： T(n) = 3logn
///以2為底 n的冪
void eat2(int n){
for(int i=1; i<n; i*=2){
System.out.println("等待一天");
System.out.println("等待一天");
System.out.println("吃一半米");
}
}
三：T(n) = 2
void eat3(int n){
System.out.println("等待一天");
System.out.println("吃一個(gè)雞腿");
}
四：T(n) = 0.5n^2 + 0.5n
void eat4(int n){
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
System.out.println("等待一天");
}
System.out.println("吃一斤米");
}
}
時(shí)間復(fù)雜度分析
有了基本操作執(zhí)行次數(shù)的函數(shù) T（n），是否就可以分析和比較一段代碼的運(yùn)行時(shí)間了呢明未？還是有一定的困難槽华。
比如算法A的相對(duì)時(shí)間是T（n）= 100n，算法B的相對(duì)時(shí)間是T（n）= 5n^2趟妥，這兩個(gè)到底誰(shuí)的運(yùn)行時(shí)間更長(zhǎng)一些猫态？這就要看n的取值了。
所以披摄，這時(shí)候有了漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complectiy）的概念亲雪，官方的定義如下：
若存在函數(shù) f（n），使得當(dāng)n趨近于無(wú)窮大時(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ù)雜度灌砖，簡(jiǎn)稱時(shí)間復(fù)雜度。
漸進(jìn)時(shí)間復(fù)雜度用大寫O來(lái)表示傀蚌，所以也被稱為大O表示法基显。
推導(dǎo)時(shí)間復(fù)雜度
如果運(yùn)行時(shí)間是常數(shù)量級(jí)，用常數(shù)1表示善炫；
只保留時(shí)間函數(shù)中的最高階項(xiàng)撩幽；
如果最高階項(xiàng)存在，則省去最高階項(xiàng)前面的系數(shù)销部。
一：T(n) = 2n
最高項(xiàng)為2n 則省出系數(shù)3 轉(zhuǎn)化為時(shí)間復(fù)雜度為 T(n) = O(n)
二：T(n) = 3logn
最高項(xiàng)為3logn 則省出系數(shù)3 轉(zhuǎn)化為時(shí)間復(fù)雜度為 T(n) = O(logn)
三：T（n） = 2
最高項(xiàng)為2 則省出系數(shù)2 轉(zhuǎn)化為時(shí)間復(fù)雜度為 T(n) = O(1)
四：T（n） = 0.5n^2 + 0.5n
最高階項(xiàng)為0.5n^2摸航，省去系數(shù)0.5制跟，轉(zhuǎn)化的時(shí)間復(fù)雜度為T（n） = O（n^2）
這四種復(fù)雜度時(shí)間耗時(shí)為
O(1) < O(logn) < O(n) < O(n^2)
除了上述的四個(gè)場(chǎng)景舅桩，還有許多不同形式的時(shí)間復(fù)雜度，比如：
O（nlogn）, O（n^3）, O（m*n）雨膨，O（2^n）擂涛，O（n！）
時(shí)間復(fù)雜度的巨大差異
例子
算法A的相對(duì)時(shí)間規(guī)模是T（n）= 100n，時(shí)間復(fù)雜度是O(n)
算法B的相對(duì)時(shí)間規(guī)模是T（n）= 5n2撒妈，時(shí)間復(fù)雜度是O(n2)
從表格中可以看出恢暖，當(dāng)n的值很小的時(shí)候，算法A的運(yùn)行用時(shí)要遠(yuǎn)大于算法B狰右；當(dāng)n的值達(dá)到1000左右杰捂，算法A和算法B的運(yùn)行時(shí)間已經(jīng)接近；當(dāng)n的值越來(lái)越大棋蚌，達(dá)到十萬(wàn)嫁佳、百萬(wàn)時(shí)，算法A的優(yōu)勢(shì)開始顯現(xiàn)谷暮，算法B則越來(lái)越慢蒿往，差距越來(lái)越明顯。
這就是不同時(shí)間復(fù)雜度帶來(lái)的差距湿弦。
