一、簡述

算法的優(yōu)劣，有兩個重要的衡量維度：

1??時間維度：是指執(zhí)行當前算法所消耗的時間，通常用時間復雜度來描述。
2??空間維度：是指執(zhí)行當前算法所占用的內(nèi)存，通常用空間復雜度【Space Complexity】來描述。

因此，評價一個算法的效率主要是看它的時間復雜度和空間復雜度情況。時間復雜度不是用來計算程序具體耗時的，空間復雜度也不是用來計算程序?qū)嶋H占用的空間的。

二、時間復雜度T(n) = O(f(n))

算法的時間復雜度，很多人以為就是該算法程序的運行時間。然而這種結(jié)果非常容易受運行環(huán)境的影響，在性能高的機器上跑出來的結(jié)果與在性能低的機器上跑的結(jié)果相差會很大。而且與測試時使用的數(shù)據(jù)規(guī)模也有很大關系。因此，更為通用的方法就應用而生：「 大O符號表示法 」，即T(n) = O(f(n))。其中 f(n) 表示每行代碼執(zhí)行次數(shù)之和，而 O 表示正比例關系，這個公式的全稱是：算法的漸進時間復雜度。先看個例子：

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

這段代碼的時間復雜度為：O(n)，為什么呢？假設每行代碼的執(zhí)行時間都是一樣的，用 1 個單位時間來表示，那么這個例子的第一行耗時是 1 個單位時間，第三行的執(zhí)行時間是 n 個單位時間，第四行的執(zhí)行時間也是 n個單位時間(第二行和第五行是符號，忽略)，那么總時間就是 1 個單位時間 + n 個單位時間 + n 個單位時間 ，即 (1+2n)個單位時間，即： T(n) = (1+2n)*單位時間，由此看出，該算法的耗時是隨著 n 的變化而變化。因此，可以將這個算法的時間復雜度簡化的表示為：T(n) = O(n)。

因為大 O 符號表示法并不是用于來真實代表算法的執(zhí)行時間的，它是用來表示代碼執(zhí)行時間的增長變化趨勢的。所以如果 n 無限大的時候，T(n) = time(1+2n) 中的常量 1 就沒有意義了，倍數(shù) 2 也意義不大。因此直接簡化為 T(n) = O(n) 就可以了。

按時間復雜度越來越大，執(zhí)行的效率越來越低排序，常見的量級有：

①常數(shù)階O(1)
②對數(shù)階O(logN)
③線性階O(n)
④線性對數(shù)階O(nlogN)
⑤平方階O(n2)
⑥立方階O(n3)
⑦K次方階O(n^k)
⑧指數(shù)階(2^n)

1??常數(shù)階O(1)
無論代碼執(zhí)行了多少行，只要是沒有循環(huán)等復雜結(jié)構(gòu)，那這個代碼的時間復雜度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代碼在執(zhí)行的時候，它消耗的時候并不隨著某個變量的增長而增長，那么無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間復雜度。

2??線性階O(n)
這個就是最開始的示例，如：

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

這段代碼，for 循環(huán)里面的代碼會執(zhí)行 n 遍，因此它消耗的時間是隨著 n 的變化而變化的，因此這類代碼都可以用O(n)來表示它的時間復雜度。

3??對數(shù)階O(logN)
還是先來看代碼：

int i = 1;
while(i<n)
{
    i = i * 2;
}

while 循環(huán)里，每次都將 i 乘以 2，乘完之后，i 距離 n 就越來越近了。假設循環(huán) x 次之后，i 就大于 n 了，此時循環(huán)退出，也就是說 2 的 x 次方等于 n，那么 x = log2^n。也就是說當循環(huán) log2^n 次以后，這個代碼就結(jié)束了。因此這個代碼的時間復雜度為：O(logn)。

4??線性對數(shù)階O(nlogN)
將時間復雜度為O(logn)的代碼循環(huán) n 遍的話，那么它的時間復雜度就是 n * O(logN)，也就是了O(nlogN)。如：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

5??平方階O(n2)
如果把 O(n) 的代碼再嵌套循環(huán)一遍，它的時間復雜度就是 O(n2) 了。如：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

這段代碼其實就是嵌套了 2 層 n 循環(huán)，它的時間復雜度就是 O(n*n)，即 O(n2)。如果將其中一層循環(huán)的 n 改成 m，即：

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的時間復雜度就變成了 O(m*n)

6??立方階O(n3) 相當于三層 n 循環(huán)、K次方階O(n^k)相當于 k 層 n 循環(huán)。

除此之外，其實還有平均時間復雜度、均攤時間復雜度、最壞時間復雜度、最好時間復雜度的分析方法。

三、空間復雜度S(n)=O(f(n))

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢，用 S(n) 來定義。空間復雜度比較常用的有：O(1)、O(n)、O(n2)。

1??空間復雜度 O(1)
如果算法執(zhí)行所需要的臨時空間不隨著某個變量 n 的大小而變化，即此算法空間復雜度為一個常量，可表示為 O(1)。如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代碼中的 i、j、m 所分配的空間都不隨著處理數(shù)據(jù)量變化，因此它的空間復雜度 S(n) = O(1)。

2??空間復雜度 O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

代碼中，第一行 new 了一個數(shù)組出來，這個數(shù)據(jù)占用的大小為 n。這段代碼的 2-6 行，雖然有循環(huán)，但沒有再分配新的空間，因此，這段代碼的空間復雜度主要看第一行即可，即 S(n) = O(n)。