原文出自：http://www.itdecent.cn/p/d72d4c9e90c6

你還在為開發(fā)中頻繁切換環(huán)境打包而煩惱嗎？快來試試 Environment Switcher 吧！使用它可以在app運(yùn)行時(shí)一鍵切換環(huán)境，而且還支持其他貼心小功能，有了它媽媽再也不用擔(dān)心頻繁環(huán)境切換了。https://github.com/CodeXiaoMai/EnvironmentSwitcher

上一章：程序猿必修課之?dāng)?shù)據(jù)結(jié)構(gòu)（一）數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語

算法

算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

算法的特性

算法具有五個(gè)基本特性：輸入、輸出、有窮性、確定性、可行性。

算法設(shè)計(jì)的要求

好的算法，應(yīng)該具有：正確性、可讀性、健壯性、高效率和低存儲(chǔ)量的特征。

函數(shù)的漸近增長

輸入規(guī)模 n 在沒有限制的情況下，只要超過一個(gè)數(shù)值 N， 這個(gè)函數(shù)就總是大于另一個(gè)函數(shù)，我們稱函數(shù)是漸近增長的。

給定兩個(gè)函數(shù) f(n) 和 g(n), 如果存在一個(gè)整數(shù) N，使得對于所有的 n > N, f(n) 總是比 g(n) 大，那么我們說 f(n) 的增長漸近快于 g(n)。

算法時(shí)間復(fù)雜度

在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù) T(n) 是關(guān)于問題規(guī)模 n 的函數(shù)，進(jìn)而分析 T(n) 隨 n 的變化情況并確定 T(n) 的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n) = O(f(n))。它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時(shí)間的增長率和 f(n) 的增長率相同，稱為算法的漸近時(shí)間復(fù)雜度，簡稱為時(shí)間復(fù)雜度。其中 f(n) 是規(guī)模 n 的某個(gè)函數(shù)。

用 O() 來體現(xiàn)算法時(shí)間復(fù)雜度的記法，叫作大 O 記法。

推導(dǎo)大 O 階方法

1. 用常數(shù) 1 取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2. 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
3. 如果最高階項(xiàng)存在且不是 1 ，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

常數(shù)階

高斯算法

int sum = 0, n = 100;   // 執(zhí)行 1 次
sum = (1 + n) * n / 2;  // 執(zhí)行 1 次
printf("%d", sum);      // 執(zhí)行 1 次

這個(gè)算法的運(yùn)行次數(shù)函數(shù)是 f(n) = 3。根據(jù)推導(dǎo)大 O 階的方法，第一步把常數(shù)項(xiàng) 3 改為 1。第二步保留最高階項(xiàng)，它沒有最高階項(xiàng)，所以這個(gè)算法的時(shí)間復(fù)雜度為 T(n) = O(1)。

當(dāng) n = 1 時(shí)，算法執(zhí)行次數(shù)為 3， 當(dāng) n = 100時(shí)，算法的執(zhí)行次數(shù)還是 3，所以我們可以看出這個(gè)算法的執(zhí)行次數(shù)與 n 的規(guī)模沒關(guān)系。我們把這種與問題的大小（n 的大小）無關(guān)，執(zhí)行時(shí)間恒定的算法， 叫作常數(shù)階。

對于分支結(jié)構(gòu)，無論是真還是假，執(zhí)行的次數(shù)都是恒定的，不會(huì)隨著 n 的變化而變化，所以單純的分支結(jié)構(gòu)（不包含在循環(huán)結(jié)構(gòu)中），其時(shí)間復(fù)雜度也是 O(1)。

線性階

下面這段代碼的時(shí)間復(fù)雜度為 O(n),因?yàn)檠h(huán)體中的代碼必須要執(zhí)行 n 次。

int i;
for (i = 0; i < n; i++) {
    /* 時(shí)間復(fù)雜度為 O(1) 的程序步驟序列 */
}

對數(shù)階

int count = 1;
while (count < n) {
    count = count * 2;
    /* 時(shí)間復(fù)雜度為 O(1) 的程序步驟序列 */
}

由于每次 count 乘以 2 以后，就越來越接近于 n，也就是說有多少個(gè) 2 相乘后大于 n，則會(huì)退出循環(huán)。由 2x = n 等到 x = log2n。所以這個(gè)算法的時(shí)間復(fù)雜度為 T(n) = O(logn)。

平方階

這是一個(gè)循環(huán)嵌套的代碼。

int i, j;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        /* 時(shí)間復(fù)雜度為 O(1) 的程序步驟序列 */
    }
}

它的內(nèi)循環(huán)我們已經(jīng)知道，時(shí)間復(fù)雜度為 O(n)，而對于外層的循環(huán)，不過是內(nèi)部這個(gè)時(shí)間復(fù)雜度為 O(n) 的語句，再循環(huán) n 次。所以這段代碼的時(shí)間復(fù)雜度為 O(n2)

如果外循環(huán)的次數(shù)改為了 m，時(shí)間復(fù)雜度就變?yōu)?O(m*n)。

int i, j， m;
for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
        /* 時(shí)間復(fù)雜度為 O(1) 的程序步驟序列 */
    }
}

所以我們可以總結(jié)得出，循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)。

下面這個(gè)循環(huán)嵌套，它的時(shí)間復(fù)雜度是多少呢？

int i, j;
for (i = 0; i < n; i++) {
    for (j = i; j < n; j++) {   // 注意 j = i 而不是 0
        /* 時(shí)間復(fù)雜度為 O(1) 的程序步驟序列 */
    }
}

由于當(dāng) i = 0 時(shí)，內(nèi)循環(huán)執(zhí)行了 n 次，當(dāng) i = 1 時(shí)，執(zhí)行了 n -1 次，…… 當(dāng) i = n - 1 時(shí)，執(zhí)行了 1 次。所以部的執(zhí)行次數(shù)為：

n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n2/2 + n/2。

用我們推導(dǎo)大 O 階的方法，第一條，沒有加法常數(shù)不考慮；第二條，只保留最高階項(xiàng)，因此保留 n2/2；第三條，去除這個(gè)項(xiàng)相乘的常數(shù)，也就是去除 1/2， 最終這個(gè)算法的時(shí)間復(fù)雜度為 T(n) = O(n2)

常見的時(shí)間復(fù)雜度

常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

算法空間復(fù)雜度

算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法空間復(fù)雜度的計(jì)算公式：S(n) = O(f(n)),其中 n 為問題的規(guī)模，f(n)為語句關(guān)于 n 所占存儲(chǔ)空間的函數(shù)。

總結(jié)

1. 算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。
2. 算法的特性：有窮性、確定性、可行性、輸入、輸出。
3. 算法的設(shè)計(jì)要求：正確性、可讀性、健壯性、高效率和低存儲(chǔ)量需求。

下一章：程序猿必修課之?dāng)?shù)據(jù)結(jié)構(gòu)（三）線性表1