用這篇博客記錄一下學(xué)習(xí)如何計(jì)算時(shí)間復(fù)雜度的過(guò)程。本文會(huì)從時(shí)間復(fù)雜度的定義到具體案例的練習(xí)，讓初學(xué)者對(duì)時(shí)間復(fù)雜度有個(gè)基本印象措嵌。
摘自《維基百科》
?
在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)芦缰，它定性描述該算法的運(yùn)行時(shí)間企巢。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述让蕾，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)浪规。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱(chēng)為是漸近的探孝，亦即考察輸入值大小趨近無(wú)窮時(shí)的情況笋婿。例如，如果一個(gè)算法對(duì)于任何大小為 n （必須比 n0 大）的輸入再姑，它至多需要 5n3 + 3n 的時(shí)間運(yùn)行完畢萌抵，那么它的漸近時(shí)間復(fù)雜度是 O(n3)。
?
為了計(jì)算時(shí)間復(fù)雜度元镀，我們通常會(huì)估計(jì)算法的操作單元數(shù)量绍填，每個(gè)單元運(yùn)行的時(shí)間都是相同的。因此栖疑，總運(yùn)行時(shí)間和算法的操作單元數(shù)量最多相差一個(gè)常量系數(shù)讨永。
?
相同大小的不同輸入值仍可能造成算法的運(yùn)行時(shí)間不同，因此我們通常使用算法的最壞情況復(fù)雜度遇革，記為 T(n) 卿闹，定義為任何大小的輸入 n 所需的最大運(yùn)行時(shí)間揭糕。
摘自《百度百科》
?
1.一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)锻霎，用T(n)表示著角，若有某個(gè)輔助函數(shù)f(n)，使得T(n)/f(n)的極限值（當(dāng)n趨近于無(wú)窮大時(shí)）為不等于零的常數(shù)旋恼，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)吏口。記作T(n)=O(f(n))，稱(chēng)O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度冰更，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度产徊。
?
分析：隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率成正比蜀细，所以 f(n) 越小舟铜，算法的時(shí)間復(fù)雜度越低，算法的效率越高奠衔。
?
2. 在計(jì)算時(shí)間復(fù)雜度的時(shí)候谆刨，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)涣觉，再找出 T(n) 的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1痴荐，log2n，n官册，n log2n ，n的平方难捌，n的三次方膝宁，2的n次方，n!）根吁，找出后员淫，f(n) = 該數(shù)量級(jí)，若 T(n)/f(n) 求極限可得到一常數(shù)c击敌，則時(shí)間復(fù)雜度T(n) = O(f(n))
下面是各種常見(jiàn)函數(shù)的時(shí)間復(fù)雜度趨勢(shì)圖：
增長(zhǎng)趨勢(shì)是 O(1) < O(log n) < O(√n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)
看過(guò)了定義概念和趨勢(shì)圖之后其實(shí)還是不太明白時(shí)間復(fù)雜度是什么介返，所以有必要把時(shí)間復(fù)雜度再說(shuō)白一點(diǎn)。挑幾個(gè)經(jīng)典的并且常見(jiàn)的時(shí)間復(fù)雜度來(lái)舉例說(shuō)明沃斤。
我理解的是計(jì)算時(shí)間復(fù)雜度時(shí)要本著幾個(gè)原則：
- 去掉（忽略）常數(shù)項(xiàng)
- 系數(shù)是常數(shù)的圣蝎，要把這個(gè)系數(shù)去掉
- 只留最高次項(xiàng)
比如 T(n) = 4n^3 + 2n^2 + 5n + 10
去掉常數(shù)項(xiàng)：T(n) = 4n^3 + 2n^2 + 5n
去掉常數(shù)系數(shù)：T(n) = n^3 + n^2 + n
只留最高次項(xiàng)：T(n) = n^3
所以最后時(shí)間復(fù)雜度為 O(n^3)
注：n^3 表示 n 的 3 次冪。
復(fù)雜度 O(1) ：常數(shù)級(jí)
例1：
- (void)printHello:(int)n {
NSLog(@"Hello world!");
}
方法中只有一句 NSLog 語(yǔ)句衡瓶，也就是說(shuō)程序執(zhí)行這段代碼的總操作單元數(shù)量(總次數(shù))恒等于常數(shù) 1徘公。代碼的執(zhí)行次數(shù)與問(wèn)題規(guī)模 n 無(wú)關(guān)，這樣的代碼段時(shí)間復(fù)雜度就是 O(1) 哮针。
例2：
- (void)conditionalStatement:(int)n {
if (n > 10) {
NSLog(@"大于 10");
}
else {
NSLog(@"不大于 10");
}
}
方法中先要對(duì)參數(shù) n 進(jìn)行判斷关面，此處要執(zhí)行一次坦袍。然后如果 n > 10 執(zhí)行 NSLog(@"大于 10");，如果 n <= 10 那么執(zhí)行 NSLog(@"不大于 10");等太。所以無(wú)論 n 等于幾捂齐，代碼段執(zhí)行的總次數(shù)恒等于常數(shù) 2∷趼眨或者說(shuō)最壞的情況（執(zhí)行次數(shù)最多的時(shí)候）也是常數(shù) 2奠宜。所以它的時(shí)間復(fù)雜度仍然是 O(1)。
復(fù)雜度 O(log n)：對(duì)數(shù)級(jí)增長(zhǎng)
例3：
- (void)exampleForLogN:(int)n {
int num1 = 0, num2 = 0;
for(int i=0; i<n; i++){
num1 += 1;
for(int j=1; j<=n; j*=2){
num2 += num1;
}
}
}
語(yǔ)句 int num1 = 0, num2 = 0; 的執(zhí)行次數(shù)（頻度）為1缝其；
語(yǔ)句 i=0; 的頻度為1挎塌；
語(yǔ)句 i<n; i++; num1+=1; j=1; 的頻度為n；
語(yǔ)句 j<=n; j*=2; num2+=num1; 的頻度為 n*log n内边；
T(n) = 2 + 1 + 4n + 3n*log n榴都，當(dāng) n 趨近無(wú)窮大時(shí)，復(fù)雜度會(huì)越來(lái)越趨近最高冪次項(xiàng) 3n*log n的值漠其，再去掉系數(shù) 3嘴高，就是我們要算的時(shí)間復(fù)雜度 O(n*log n)。
其中最內(nèi)層的 num2+=num1; 是執(zhí)行最多的語(yǔ)句和屎，它的執(zhí)行次數(shù)為什么是 n*log n 呢拴驮？
分析一下：語(yǔ)句 num2+=num1; 處在兩層嵌套的循環(huán)之中，如果外層循環(huán)次數(shù)為 n 柴信，內(nèi)層循環(huán)次數(shù)為 m 套啤，那么語(yǔ)句 num2+=num1; 就會(huì)執(zhí)行 n * m次。代碼中很容易看出來(lái)外層循環(huán)就是執(zhí)行 n 次随常，而內(nèi)層循環(huán)到底執(zhí)行了多少次取決于 j*=2 這句代碼的趨勢(shì)潜沦。j 從 1 開(kāi)始計(jì)數(shù)，j 的變化趨勢(shì)是 j=2 --> j=4 --> j=8 --> j=16... 也就是 j是以指數(shù)趨勢(shì)增長(zhǎng)绪氛，假設(shè)當(dāng) j = n 時(shí)執(zhí)行了 t 次唆鸡，那么就有 2^t=n（2 的 t 次冪等于 n），則有次數(shù) t=log n（log 以 2 為底 n 的對(duì)數(shù)）枣察，也就是說(shuō)問(wèn)題規(guī)模為 n 時(shí)争占，內(nèi)層循環(huán)執(zhí)行了 log n 次，所以?xún)?nèi)外層相乘即n*log n序目。
復(fù)雜度 O(n)：線性增長(zhǎng)
例4：
- (void)exampleForSum:(int)n {
int sum = 1;
for (int i = 0; i < n; i++) {
sum += i;
}
NSLog(@"%d", sum);
}
語(yǔ)句 int sum = 1; 執(zhí)行 1 次臂痕；
語(yǔ)句 int i = 0; 執(zhí)行 1 次；
語(yǔ)句 i < n; i++ sum += i; 都會(huì)執(zhí)行 n 次宛琅；
語(yǔ)句 NSLog(@"%d", sum); 執(zhí)行 1 次刻蟹；
所以 T(n)=3+3n，當(dāng) n 趨近無(wú)窮大時(shí)嘿辟，有復(fù)雜度 T(n) = O(n)舆瘪，即這段代碼的時(shí)間復(fù)雜度是 O(n)片效。
例5：
- (NSInteger)findMaxElement:(NSArray *)array {
NSInteger max = [array.firstObject integerValue];
for (int i = 0; i < array.count; i++) {
if ([array[i] integerValue] > max) {
max = [array[i] integerValue];
}
}
return max;
}
n 為數(shù)組 array 的元素個(gè)數(shù)，則最壞情況下需要比較 n 次以得到最大值英古，所以算法復(fù)雜度為 O(n)淀衣。
例6：
int factorial(int n) {
if (n == 0) {
return 1;
}
else {
return n * factorial(n - 1);
}
}
階乘：給定規(guī)模 n，算法基本步驟執(zhí)行的數(shù)量為 n召调，所以算法復(fù)雜度為 O(n)膨桥。
復(fù)雜度 O(n^2)：乘方級(jí)增長(zhǎng)
例7：
- (NSInteger)SumMN:(NSInteger)n {
NSInteger sum = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
sum += x * y;
}
}
return sum;
}
給定規(guī)模 n ，則基本步驟的執(zhí)行數(shù)量為 n*n唠叛，所以算法復(fù)雜度為 O(n^2)只嚣。
例8：
- (NSInteger)findInversions:(NSArray *)array {
NSInteger inversions = 0;
for (int i = 0; i < array.count; i++) {
for (int j = i + 1; j < array.count; j++) {
if (array[i] > array[j]) {
inversions++;
}
}
}
return inversions;
}
單位操作if語(yǔ)句在兩層for循環(huán)中，它的總次數(shù)是一個(gè)等差數(shù)列之和艺沼，即首數(shù)加尾數(shù)乘以個(gè)數(shù)除以2册舞。
當(dāng)i=0時(shí)，內(nèi)層執(zhí)行(n-1)次障般，當(dāng)i=n-1時(shí)调鲸，內(nèi)層執(zhí)行 0 次，首數(shù)加尾數(shù)(n-1+0),乘以個(gè)數(shù)除以2挽荡，T(n) = (n-1)*n/2藐石。
n 為數(shù)組 array 的大小，則基本步驟的執(zhí)行數(shù)量約為 n*(n-1)/2定拟，所以算法復(fù)雜度為 O(n2)于微。
復(fù)雜度 O(2^n)：指數(shù)級(jí)增長(zhǎng)
例9：
- (NSInteger)Calculation:(NSInteger)n {
NSInteger result = 0;
for (int i = 0; i < (1 << n); i++) {
result += i;
}
return result;
}
例子中 i 的循環(huán)條件是 i < (1 << n)，1 << n 表示二進(jìn)制的 1 --> 0001 向左移 n 位青自。比如 n = 1 時(shí)向左移 1 位是 0010 角雷，十進(jìn)制就是 2，循環(huán)體執(zhí)行 2 次性穿。n = 2 時(shí)向左移 2 位是 0100，十進(jìn)制就是 4 雷滚，循環(huán)體執(zhí)行4次需曾。所以循環(huán)次數(shù)是 2^n，復(fù)雜度是 O(2^n)祈远。
例10：
- (NSUInteger)fibonacci:(NSUInteger)n {
if (n < 2) {
return n;
}
else {
return [self fibonacci:n-1] + [self fibonacci:n-2];
}
}
這個(gè)是斐波那契數(shù)列的遞歸調(diào)用求解方式呆万。當(dāng) n<2 時(shí)執(zhí)行次數(shù)是一個(gè)常數(shù)，即只執(zhí)行一步返回 n 即可车份，復(fù)雜度為 O(1)谋减。當(dāng) n>=2 時(shí)，n 會(huì)被一層一層拆分扫沼，一直拆分為 1 或 0 時(shí)才能被確定值出爹。如圖：
通過(guò)圖片能看出總執(zhí)行次數(shù)在以指數(shù)級(jí)增長(zhǎng)庄吼，所以復(fù)雜度是 O(2^n)。
小訓(xùn)練
測(cè)試1：
- (void)smallTest1 {
int i = 2;
int j = 4;
int temp = i;
i = j;
j = temp;
}
以上三條單個(gè)語(yǔ)句的頻度為1严就，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)总寻。
算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)梢为。
如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)渐行，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)铸董。
此類(lèi)算法的時(shí)間復(fù)雜度是O(1)祟印。
測(cè)試2：
- (void)smallTest2:(int)n {
int sum = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum++;
}
}
}
單純的雙層循環(huán)嵌套，復(fù)雜度 O(n^2)粟害。
測(cè)試3：
- (void)smallTest3:(int)n {
int y = 1;
int x = 1;
for (int i = 1 ; i < n; i++) {
y++; // 語(yǔ)句 1
for (int j = 0; j < (2*n); j++) {
x++; // 語(yǔ)句 2
}
}
}
語(yǔ)句1的頻度是n-1;
語(yǔ)句2的頻度是(n-1)*(2n+1) = 2n^2-n-1;
T(n) = 2n^2-n-1+(n-1) = 2n^2-2;
f(n) = n^2;
lim(T(n)/f(n)) = 2 + 2*(1/n^2) = 2;
T(n) = O(n^2).
測(cè)試4：
- (void)smallTest4:(int)n {
int i = 1; // 語(yǔ)句 1
while (i <= n) {
i = i*2; // 語(yǔ)句 2
}
}
語(yǔ)句1的頻度是1,
設(shè)語(yǔ)句2的頻度是t, 則：2^t <= n; t <= log_2^n
考慮最壞情況蕴忆，取最大值t=log_2^n,
T(n) = 1 + log_2^n
f(n) = log_2^n
lim(T(n)/f(n)) = 1/log_2^n + 1 = 1
T(n) = O(log n)
注：log_2^n表示 log 以 2 為底 n 的對(duì)數(shù)。
測(cè)試5：
- (void)smallTest5:(int)n {
int x = 0;
for(int i=0;i<n;i++) {
for(int j=0;j<i;j++) {
for(int k=0;k<j;k++) {
x=x+2;
}
}
}
}
我沒(méi)有算出來(lái)這個(gè)數(shù)列的求總和到底是什么公式我磁。不過(guò)可以通過(guò)觀察孽文，能知道這個(gè)算法是三層循環(huán)嵌套，最內(nèi)層是O(1)復(fù)雜度的執(zhí)行語(yǔ)句夺艰，第二層和第三層不是以乘方遞減芋哭，所以最多是O(n^3)。如果哪位大神指導(dǎo)具體的求和公式是什么還希望不吝賜教??郁副！
