時(shí)間復(fù)雜度
度量一個程序(算法)執(zhí)行時(shí)間的兩種方法
事后統(tǒng)計(jì)的方法
這種方法可行, 但是有兩個問題：一是要想對設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評測，需要實(shí)際運(yùn)行該程序瑞你；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素, 這種方式盈电，要在同一臺計(jì)算機(jī)的相同狀態(tài)下運(yùn)行，才能比較那個算法速度更快。
事前估算的方法
通過分析某個算法的時(shí)間復(fù)雜度來判斷哪個算法更優(yōu).
時(shí)間頻度
基本介紹
時(shí)間頻度：一個算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例裕循，哪個算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多净刮。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度剥哑。記為T(n)。
計(jì)算規(guī)則介紹:
-
忽略常數(shù)項(xiàng)
image 舉例說明-忽略低次項(xiàng)
- 舉例說明-忽略系數(shù)
一般情況下淹父，算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)星持，用T(n)表示，若有某個輔助函數(shù)f(n)弹灭，使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)揪垄，則稱f(n)是T(n)的同數(shù)量級函數(shù)穷吮。記作 T(n)=Ｏ( f(n) )，稱Ｏ( f(n) ) 為算法的漸進(jìn)時(shí)間復(fù)雜度饥努，簡稱時(shí)間復(fù)雜度捡鱼。
T(n) 不同，但時(shí)間復(fù)雜度可能相同酷愧。 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的T(n) 不同驾诈，但時(shí)間復(fù)雜度相同，都為O(n2)溶浴。
計(jì)算時(shí)間復(fù)雜度的方法：
用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù) T(n)=n2+7n+6 => T(n)=n2+7n+1
修改后的運(yùn)行次數(shù)函數(shù)中乍迄，只保留最高階項(xiàng) T(n)=n2+7n+1 => T(n) = n2
去除最高階項(xiàng)的系數(shù) T(n) = n2 => T(n) = n2 => O(n2)
常見的時(shí)間復(fù)雜度
1.常數(shù)階
常數(shù)階O(1)
無論代碼執(zhí)行了多少行，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)士败，那這個代碼的時(shí)間復(fù)雜度就都是O(1)
上述代碼在執(zhí)行的時(shí)候闯两，它消耗的時(shí)候并不隨著某個變量的增長而增長，那么無論這類代碼有多長谅将，即使有幾萬幾十萬行漾狼，都可以用O(1)來表示它的時(shí)間復(fù)雜度。
2.對數(shù)階對數(shù)階O(log2n)
說明：在while循環(huán)里面饥臂，每次都將 i 乘以 2逊躁，乘完之后，i 距離 n 就越來越近了隅熙。假設(shè)循環(huán)x次之后稽煤，i 就大于 2 了核芽，此時(shí)這個循環(huán)就退出了，也就是說 2 的 x 次方等于 n念脯，那么 x = log2n也就是說當(dāng)循環(huán) log2n 次以后狞洋，這個代碼就結(jié)束了。因此這個代碼的時(shí)間復(fù)雜度為：O(log2n) 绿店。 O(log2n) 的這個2 時(shí)間上是根據(jù)代碼變化的吉懊，i = i * 3 ，則是 O(log3n) .
3.線性階O(n)
說明：這段代碼假勿，for循環(huán)里面的代碼會執(zhí)行n遍借嗽，因此它消耗的時(shí)間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時(shí)間復(fù)雜度转培。
4.線性對數(shù)階O(nlogN)
說明：線性對數(shù)階O(nlogN) 其實(shí)非常容易理解恶导，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logN)浸须，也就是了O(nlogN)
5.平方階O(n2)
說明：平方階O(n2) 就更容易理解了惨寿，如果把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2)删窒，這段代碼其實(shí)就是嵌套了2層n循環(huán)裂垦，它的時(shí)間復(fù)雜度就是 O(n * n)，即 O(n2) 如果將其中一層循環(huán)的n改成m肌索，那它的時(shí)間復(fù)雜度就變成了 O(m * n)
6.立方階O(n3)蕉拢、K次方階O(n^k)
參考上面的O(n2) 去理解。
平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下诚亚，該算法的運(yùn)行時(shí)間晕换。
最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度站宗。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限闸准，這就保證了算法的運(yùn)行時(shí)間不會比最壞情況更長。
平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一致梢灭，和算法有關(guān)(如圖:)恕汇。
八大算法的時(shí)間復(fù)雜度總結(jié)
算法的空間復(fù)雜度簡介
基本介紹
類似于時(shí)間復(fù)雜度的討論，一個算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費(fèi)的存儲空間或辖，它也是問題規(guī)模n的函數(shù)瘾英。
空間復(fù)雜度(Space Complexity)是對一個算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的量度。有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān)颂暇，它隨著n的增大而增大缺谴，當(dāng)n較大時(shí)，將占用較多的存儲單元，例如快速排序和歸并排序算法就屬于這種情況
在做算法分析時(shí)湿蛔，主要討論的是時(shí)間復(fù)雜度膀曾。從用戶使用體驗(yàn)上看，更看重的程序執(zhí)行的速度阳啥。一些緩存產(chǎn)品(redis, memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時(shí)間.
待續(xù)
