數據結構--時間/空間複雜度

一. 時間複雜度

• 時間複雜度簡單的說就是一個程式運行所消耗的時間，叫做時間複雜度，我們無法目測一個程式具體的時間複雜度，但是我們可以估計大概的時間複雜度。
• 一段好的代碼的就根據演算法的時間複雜度，即使在大量數據下也能保持高效的運行速率，這也是我們學習演算法的必要性。

1.1 大O表示法

我們來看看下麵這代碼的時間複雜度

void Func1(int N) 
{
    int count = 0;
    for (int i = 0; i < N; ++i) 
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }
    for (int k = 0; k < 2 * N; ++k) 
    {
        ++count;
    }
    int M = 10;
    while (M--) 
    {
        ++count;
    }
    printf("%d\n", count);
}

這個函數在調用的過程中使用了三個for迴圈和一個while迴圈，每迴圈一次我們說它進行了一次基本操作。那麼這個函數執行基本操作的次數為F(N)=N²+2*N+10

• 推導大O階方法：

  • 用常數1取代運行時間中的所有加法常數。
  • 在修改後的運行次數函數中，只保留最高階項。
  • 如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。

• 按照上面的規則，那麼上述代碼的時間複雜度就為O(N²)。

• 我們發現，通過上面的規則，我們就使用N²來代替了N²+2*N+10，我們為什麼要這樣規定呢，我們以上面的表達式為例，當N為不同的值時，表達式的結果為多少

eg:
N=100 F(N)=10210
N=1000 F(N)=1002010
N=10000 F(N)=100020010

我們發現，當N不斷變大時，表達式的值也不斷變大，而對錶達式的結果影響最大的一項就是這個表達式中階數最高的那一項。

二. 空間複雜度

• 簡單的說就是程式運行所需要的空間。
• 寫代碼我們可以用時間換空間，也可以用空間換時間。加大空間消耗來換取運行時間的縮短加大時間的消耗換取空間，我們一般選擇空間換時間。一般說複雜度是指時間複雜度。

2.1 空間複雜度的定義

空間複雜度是對一個演算法在運行過程中臨時占用存儲空間大小的量度 。空間複雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間複雜度算的是變數的個數。空間複雜度計算規則基本跟實踐複雜度類似，也使用大O漸進表示法。

我們以冒泡排序舉例：

void BubbleSort(int* a, int n) 
{
     assert(a);
     for (size_t end = n; end > 0; --end)
     {
         int exchange = 0;
         for (size_t i = 1; i < end; ++i)
         {
             if (a[i-1] > a[i])
             {
                 Swap(&a[i-1], &a[i]);
                 exchange = 1;
             }
         }
         if (exchange == 0)
         break;
     }
}

根據定義我們知道，空間複雜度是用來估算占用空間的大小的，那麼我們就可以根據演算法中創建的變數的個數來表示演算法的空間複雜度，這個冒泡排序演算法創建了3個變數，根據大O的漸進表示法的規則，該演算法的空間複雜度就為O(1)。

我們在以斐波那契數列為例：

long long* Fibonacci(size_t n) 
{
    if (n == 0)
        return NULL;

    long long* fibArray =(long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1; for (int i = 2; i <= n; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;
}

//這就是迴圈方法計算斐波那契數的代碼，我們發現在這個演算法中，我們使用malloc開闢了一塊元素個數為n+1的空間，那就相當於創建了n+1個變數，根據大O的線性表示法，該演算法的空間複雜度就為O(N)。

那麼我們使用遞歸的方法時的空間複雜度又是多少呢

long long Factorial(size_t N) 
{
     return N < 2 ? N : Factorial(N-1)*N; 
}
//我們知道在調用函數時，是會創建棧幀的，簡單來說就是我們每調用一次函數，就會為調用的那個函數創建一塊空間，在計算遞歸演算法的空間複雜度時，我們可以認為每次函數調用時都會創建常數個變數，那麼影響我們演算法空間複雜度的就是我們調用遞歸的次數，那麼以上面的演算法為例，該演算法的空間複雜度就是O(N)。遞歸演算法的空間複雜度通常是遞歸的深度

空間複雜度一般只有兩種情況：
創建了常數個變數：O(1)
創建了N個變數：O(N)