演算法學習-1 演算法複雜度

一 演算法複雜度

演算法複雜度分為時間複雜度和空間複雜度。時間複雜度是指執行演算法所需要的計算工作量；而空間複雜度是指執行這個演算法所需要的記憶體空間。

演算法的複雜性體運行該演算法時的電腦所需資源的多少，電腦資源最重要的是時間和空間（即寄存器）資源，因此複雜度分為時間和空間複雜度。

二 時間複雜度

2.1 關於時間複雜度

一個演算法花費的時間與演算法中語句的執行次數成正比例，演算法中語句執行次數越多，它花費時間就越多。一個演算法中的語句執行次數稱為語句時間頻度。記為T(n)。

假設演算法的問題規模為n，演算法中操作單元的數量用函數 f(n) 來表示，當n趨近於無窮大時，T(n) / f(n) 的極限值為不等於零的常數，

即隨著數據規模n的增大，演算法執行時間的增長率和 f(n)  的增長率相同，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))。

則稱O(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度(Time complexity)。

時間複雜度用大O符號(big O)表述，不包括f(n)函數的低階項和首項繫數。

不同的數據規模n可能造成演算法的運行時間不同，因此通常使用演算法的最壞情況來估計時間複雜度。

2.2 常數操作

常數時間的操作:一個操作如果和樣本的數據量沒有關係，每次都是固定時間內完成操作，叫做常數操作。

常數時間的操作是指演算法代碼中的指令都是固定時間的操作，指令是和數據量沒有關係，比如加、減、乘、除、模、位運算，或數組的定址。

2.3 常數時間

若對於一個演算法，T(n)的上界與輸入n的大小無關，則稱其具有常數時間，記作O(1)時間。例如訪問數組中的單個元素，是常數因為訪問它只需要一條指令。

但是，找到無序數組中的最小元素則不是，因為這需要遍歷所有元素來找出最小值。這是一項線性時間的操作，也稱O(n)時間。

int i = 1;
int j = 2;
i = j++;
j = j << 2;
int m = (i + j) / 2;

2.4 線性時間

如果一個演算法的時間複雜度為O(n)，則稱這個演算法具有線性時間，或O(n)時間。這意味著對於足夠大的輸入，運行時間增加的大小與輸入成線性關係。

例如，一個計算列表所有元素的和的程式，需要的時間與列表的長度成正比。

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

2.5 對數時間

若演算法的T(n) = O(log n)，則稱其具有對數時間。由於電腦使用二進位的記數系統，未寫明底數時，預設以2為底。

常見的具有對數時間的演算法有二叉樹的相關操作和二分查找。

對數時間的演算法是非常有效的，因為每增加一個輸入，其所需要的額外計算時間會變小。

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

2.6 線性對數時間

若演算法時間複雜度T(n) = O(nlog n)，則稱這個演算法具有線性對數時間。線性對數時間增長得比線性時間要快，但是對於任何含有n，且n的冪指數大於1的多項式時間來說，線性對數時間增長得慢。

例如方法Method1

void Method1(int n)
{
    for (int i = 0; i < n; i++)
    {
        Method2(n);
    }
}

void Method2(int n)
{
    for (int j = 1; j <= n; j = j * 2)
    {
        Console.WriteLine(j);
    }
}

二 空間複雜度

空間複雜度(Space Complexity)：是對一個演算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。

比如插入的時間複雜度是O(n^2),空間複雜度是O(1) 。而一般的遞歸演算法的空間複雜度為O(n)，因為每次遞歸都要存儲返回信息。

例，空間複雜度O(1)

int i = 1;
int j = 2;
i = j++;
j = j << 2;
int m = (i + j) / 2;

空間複雜度O(n)

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

以上。