一文聊聊演算法的時間複雜度與空間複雜度

這篇文章來了解演算法，介紹一下演算法的時間複雜度和空間複雜度，希望對大家有幫助！

演算法（Algorithm）是指用來操作資料、解決程式問題的一組方法。對於同一個問題，使用不同的演算法，也許最終得到的結果是一樣的，但在過程中消耗的資源和時間卻會有很大的差異。

那我們該如何衡量不同演算法之間的優劣呢？

主要還是從演算法所佔用的「時間」和「空間」兩個維度去考慮。

• 時間維度：是指執行目前演算法所消耗的時間，我們通常用「時間複雜度」來描述。

• 空間維度：是指執行目前演算法需要佔用多少記憶體空間，我們通常用「空間複雜度」來描述。

因此，評估演算法的效率主要是看它的時間複雜度和空間複雜度情況。然而，有的時候時間和空間卻又是「魚和熊掌」，不可兼得的，那麼我們就需要從中去取一個平衡點。

下面我來分別介紹一下「時間複雜度」和「空間複雜度」的計算方式。

一、時間複雜度

我們想要知道一個演算法的「時間複雜度」，很多人首先想到的的方法就是把這個演算法程式運行一遍，那麼它所消耗的時間就自然而然知道了。

這種方式可以嗎？當然可以，不過它也有很多弊端。

這種方式非常容易受運行環境的影響，在性能高的機器上跑出來的結果與在性能低的機器上跑的結果相差會很大。而且測試時使用的資料規模也有很大關係。再者，並且我們在寫演算法的時候，還沒有辦法完整的去運行。

因此，另一個更通用的方法就出來了：「 大O符號表示法 」，即T(n) = O(f(n))

我們先來看個例子：

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

透過「大O符號表示法」，這段程式碼的時間複雜度為：O(n) ，為什麼呢?

在大O符號表示法中，時間複雜度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行程式碼執行次數之和，而O 表示正比例關係，這個公式的全名是：演算法的漸進時間複雜度。

我們繼續看上面的例子，假設每行程式碼的執行時間都是一樣的，我們用1顆粒時間來表示，那麼這個例子的第一行耗時是1個顆粒時間，第三行的執行時間是n個顆粒時間，第四行的執行時間也是n個顆粒時間（第二行和第五行是符號，暫時忽略），那麼總時間就是1顆粒時間n顆粒時間n顆粒時間，即(1 2n)個顆粒時間，即： T(n) = (1 2n)*顆粒時間，從這個結果可以看出，這個演算法的耗時是隨著n的變化而變化，因此，我們可以簡化的將這個演算法的時間複雜度表示為：T(n) = O(n)

為什麼可以這麼去簡化呢，因為大O符號表示法並不是用來真實代表演算法的執行時間的，它是用來表示程式碼執行時間的成長變化趨勢的。

所以上面的例子中，如果n無限大的時候，T(n) = time(1 2n)中的常數1就沒有意義了，倍數2也意義不大。因此直接簡化為T(n) = O(n) 就可以了。

常見的時間複雜度量級有：

• 常數階O(1)

• 對數階O(logN )

• 線性階O(n)

• #線性對數階O(nlogN)

• 平方階O(n²)

• 立方階O(n³)

• K次方階O(n^k)

• 指數階(2^n)

上面從上到下依序的時間複雜度越來越大，執行的效率越來越低。

下面選取一些較為常用的來講解一下（沒有嚴格按照順序）：

• #常數階O(1)

無論程式碼執行了多少行，只要是沒有循環等複雜結構，那這個程式碼的時間複雜度就都是O(1)，如：

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

上述程式碼在執行的時候，它消耗的時候並不隨著某個變數的成長而成長，那麼無論這類程式碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間複雜度。

• 線性階O(n)

這個在最開始的程式碼範例中就講解過了，如：

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

這段程式碼，for迴圈裡面的程式碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類程式碼都可以用O(n)來表示它的時間複雜度。

• 對數階O(logN)

#還是先來看程式碼：

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

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

• 线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

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

• 平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

举例：

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

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)

如果将其中一层循环的n改成m，即：

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

那它的时间复杂度就变成了 O(m*n)

• 立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

• 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

举例：

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

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

• 空间复杂度 O(n)

我们先看一个代码：

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

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

以上，就是对算法的时间复杂度与空间复杂度基础的分析，欢迎大家一起交流。

更多算法相关知识，请访问：编程入门！！

以上是一文聊聊演算法的時間複雜度與空間複雜度的詳細內容。更多資訊請關注PHP中文網其他相關文章！