算法複雜度分析

陌客& 2021-09-19 13:19:33 阅读数:629

算法 分析

複雜度分析

​ 算法的複雜度指的是執行該算法的程序在運行時所需要的時間和空間(內存)資源,複雜度分析主要是從時間複雜度空間複雜度兩個層面來考慮。

大O(big O)錶示法

​ 在了解時間複雜度之前,我們需要知道怎麼用數學符號將它錶示出來。

​ 我們知道,一個算法的執行時間 = 該算法中每條語句執行時間之和。假設每條語句執行一次所需要的時間為單比特時間,那麼一個算法的執行時間就和算法中需要執行語句的次數成正比,即是等於所有語句的頻度(執行次數)之和。

​ 用T[n]錶示代碼的執行時間,n錶示數據規模的大小,f(n)錶示每行代碼執行的次數總和,算法執行時間的公式為:
$$
T[n] = O(f(n))
$$
​ O錶示的是代碼執行時間隨數據規模增長的變化趨勢,也叫做漸進時間複雜度(asymptotic time complexity),簡稱時間複雜度. 下面我們看一個具體的例子:

public int GetSum(int n)
{
int sum = 0;
int i = 0;
int j = 0;
for(; i < n; i++)
{
sum += i;
for(; j < n; j++)
{
sum = sum + i * j;
}
}
return sum;
}

​ 在上面例子中,由於已經假設每條語句執行一次所需時間為單比特時間,第3,4,5行執了一次,第6,8行分別執行了n次,第9,11行分別執行了n^2次,可以得出
$$
T(n) = O(2n^2 + 2n + 3)
$$
​ 當n的值非常大時,比如n=100000或者更大時,公式中的低階,常數和系數三部分並不左右增長趨勢,因此可以忽略不計,簡單點,我們可以將公式錶示為:
$$
T(n) = O(n^2)
$$

很多時候,在求一個算法的時間複雜度時,我們都會將n看作一個很大的數,因此只要它的高階項,不要低階項,也不要高階的系數,在後面的例子中還會有所體現.

時間複雜度分析

​ 前面我們已經知道了big O錶示法的由來以及如何錶示,下面我們具體講解如何計算一段代碼的時間複雜度.我們只需要記住它的一條原則:只要高階項,不要低階項,也不要高階項的系數.

​ 為什麼可以這麼說呢?因為前面已經說過了,big O錶示法只是錶示一種變化趨勢,當執行次數n變得無窮大時,整個變化趨勢基本上是由高階項所决定的,低階項對它的影響微乎其微.看下面幾個例子

public int cal(int n)
{
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p)
{
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q)
{
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i)
{
j = 1;
for (; j <= n; ++j)
{
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}

​ 根據上面的法則,我們可以輕易的得出,它的時間複雜度為 O(n^2)

​ 再看一個例子:

public int cal(int n)
{
int ret = 0;
int i = 1;
for (; i < n; ++i)
{
ret = ret + f(i);
}
}
private int f(int n)
{
int sum = 0;
int i = 1;
for (; i < n; ++i)
{
sum = sum + i;
}
return sum;
}

​ 函數cal的時間複雜度是多少呢? 第一個for循環裏面嵌套了一個函數,嵌套的函數中又有一個for循環,因此時間複雜度為O(n^2)

常見時間複雜度分析

​ 下面是常見的幾種複雜度,簡單解釋其中的幾種

  • O(1) : 錶示常量級的時間複雜度,並不是說只執行了一條語句,只要執行語句的數量是常量,都可以用它來錶示
  • O(logn) : 對數級,在分析複雜度時,不管對數的底是多少,根據數學公式,都可以將其化成底為2的對數,而在big O錶示法中,我們忽略系數,所以在對數階時間複雜度的錶示方法中,統一為O(logn)

時間複雜度的四種類型

​ 大部分代碼的複雜度分析按照上述法則分析都足以應付,但對於少部分代碼,它們的時間複雜度會隨著輸入數據的順序,比特置不同而存在量級的差距.在這種情况下,我們才需要使用到最好時間複雜度,最壞時間複雜度,平均時間複雜度,均攤時間複雜度去分析這部分代碼.

​ 看這個例子,思考一下它的時間複雜度該怎麼錶示呢?

public int find(int[] array, int x)
{
int i = 0;
int pos = -1;
for (; i < array.Length; ++i)
{
if (array[i] == x)
{
pos = i;
break;
}
}
return pos;
}

​ 代碼很簡單,遍曆數組array,查看是否存在值為x的數字,如果有,返回其下標,否則返回-1.

​ 如果數組中第一個元素的值等於x,則它的時間複雜度是O(1),如果數組中不存在值等於x的元素,則它的時間複雜度為O(n),也就是說,在不同情况下,它的複雜度不一樣,因此我們需要分情况進行討論

最好時間複雜度

​ 指的是在理想情况(最好情况)下,執行這段代碼的時間複雜度,上面例子中,它的最好時間複雜度為O(1).

最壞時間複雜度

​ 指的是在最壞情况下,執行這段代碼的時間複雜度,上面例子中,它的最壞時間複雜度為O(n).

平均時間複雜度

​ 指的是概率論中的加權平均值,也叫作期望值,所以平均時間複雜度的全稱應該叫加權平均時間複雜度或者期望時間複雜度,它的公式如下。

​ 其中A(n)錶示平均時間複雜度,S是規模為n的實例集,實例I∈S的概率為PI,算法對實例I執行的基本運算次數是tI

​ 上面排序算法中,有 n+1 種情况(在數組中有 n 種情况,不在數組中有 1 種情况),我們分別需要查找 [公式] 次。假設每種情况出現的概率都一樣,那所有的查找次數平均下來即為 [公式] ,加權平均和為 [公式] ,根據我們前面時間複雜度的加法原則,我們去掉低階項,去掉系數以後這種情况最終時間複雜度的大小為 [公式]

​ 上面的例子結論雖然是正確的,由於 n + 1 種情况出現的概率不一樣,因此並不能按照上面的方式進行計算。首先我們知道,要查找一個數,這個數要麼在數組中,要麼不在數組中,為了方便理解,我們假設它們的概率都是1/2,如果在數組中,被遍曆到的概率是1/n (因為有n個比特置,每個比特置出現的概率都相同), 所以數據被查找到的概率是1/2 * 1/n1/2n,所以它的平均複雜度的計算過程為:

均攤時間複雜度

​ 均攤時間複雜度(amortized time complexity),它對應的分析方法為攤還分析或者平攤分析。

​ 聽起來與平均時間複雜度有點類似,比較容易弄混,平均複雜度只在某些特殊情况下才會用到,而均攤時間複雜度應用的場景比它更加特殊、更加有限。

​ 對一個數據結構進行一組連續操作中,大部分情况下時間複雜度都很低,只有個別情况下時間複雜度比較高,而且這些操作之間存在前後連貫的時序關系,這個時候,我們就可以將這一組操作放在一塊兒分析,看是否能將較高時間複雜度那次操作的耗時,平攤到其他那些時間複雜度比較低的操作上。而且,在能够應用均攤時間複雜度分析的場合,一般均攤時間複雜度就等於最好情况時間複雜度。

空間複雜度分析

​ 時間複雜度的全稱是漸進時間複雜度,錶示算法的執行時間與數據規模之間的增長關系。類比一下,空間複雜度全稱就是漸進空間複雜度(asymptotic space complexity),錶示算法的存儲空間與數據規模之間的增長關系。它的分析規則與時間複雜度一樣,也是只要高階項,不要低階項,也不要高階項的系數,看下面的例子:

public void print(int n)
{
int i = 0;
int[] a = new int[n];
for (; i < n; ++i)
{
a[i] = i * i;
}
for (i = n - 1; i >= 0; --i)
{
Console.WriteLine(a[i]);
}
}

​ 顯而易見,其忽略低階項和常數項,其空間複雜度為 O(n)

總結

版权声明:本文为[陌客&amp;]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919131933423z.html