C++空間復(fù)雜度

「空間復(fù)雜度 space complexity」用于衡量算法占用內(nèi)存空間隨著數(shù)據(jù)量變大時的增長趨勢。這個概念與時間復(fù)雜度非常類似，只需將“運行時間”替換為“占用內(nèi)存空間”。

算法相關(guān)空間

算法在運行過程中使用的內(nèi)存空間主要包括以下幾種。

• 輸入空間：用于存儲算法的輸入數(shù)據(jù)。
• 暫存空間：用于存儲算法在運行過程中的變量、對象、函數(shù)上下文等數(shù)據(jù)。
• 輸出空間：用于存儲算法的輸出數(shù)據(jù)。

一般情況下，空間復(fù)雜度的統(tǒng)計范圍是“暫存空間”加上“輸出空間”。

暫存空間可以進一步劃分為三個部分。

• 暫存數(shù)據(jù)：用于保存算法運行過程中的各種常量、變量、對象等。
• 棧幀空間：用于保存調(diào)用函數(shù)的上下文數(shù)據(jù)。系統(tǒng)在每次調(diào)用函數(shù)時都會在棧頂部創(chuàng)建一個棧幀，函數(shù)返回后，棧幀空間會被釋放。
• 指令空間：用于保存編譯后的程序指令，在實際統(tǒng)計中通常忽略不計。

在分析一段程序的空間復(fù)雜度時，我們通常統(tǒng)計暫存數(shù)據(jù)、棧幀空間和輸出數(shù)據(jù)三部分。

圖 2-15   算法使用的相關(guān)空間

/* 結(jié)構(gòu)體 */
struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(nullptr) {}
};

/* 函數(shù) */
int func() {
    // 執(zhí)行某些操作...
    return 0;
}

int algorithm(int n) {        // 輸入數(shù)據(jù)
    const int a = 0;          // 暫存數(shù)據(jù)（常量）
    int b = 0;                // 暫存數(shù)據(jù)（變量）
    Node* node = new Node(0); // 暫存數(shù)據(jù)（對象）
    int c = func();           // 棧幀空間（調(diào)用函數(shù)）
    return a + b + c;         // 輸出數(shù)據(jù)
}

推算方法

空間復(fù)雜度的推算方法與時間復(fù)雜度大致相同，只需將統(tǒng)計對象從“操作數(shù)量”轉(zhuǎn)為“使用空間大小”。

而與時間復(fù)雜度不同的是，我們通常只關(guān)注最差空間復(fù)雜度。這是因為內(nèi)存空間是一項硬性要求，我們必須確保在所有輸入數(shù)據(jù)下都有足夠的內(nèi)存空間預(yù)留。

觀察以下代碼，最差空間復(fù)雜度中的“最差”有兩層含義。

1. 以最差輸入數(shù)據(jù)為準：當 n<10 時，空間復(fù)雜度為 O(1) ；但當 n>10 時，初始化的數(shù)組 nums 占用 O(n) 空間；因此最差空間復(fù)雜度為 O(n) 。
2. 以算法運行中的峰值內(nèi)存為準：例如，程序在執(zhí)行最后一行之前，占用 O(1) 空間；當初始化數(shù)組 nums 時，程序占用 O(n) 空間；因此最差空間復(fù)雜度為 O(n) 。

void algorithm(int n) {
    int a = 0;               // O(1)
    vector<int> b(10000);    // O(1)
    if (n > 10)
        vector<int> nums(n); // O(n)
}

在遞歸函數(shù)中，需要注意統(tǒng)計棧幀空間。例如在以下代碼中：

• 函數(shù) loop() 在循環(huán)中調(diào)用了 n 次 function() ，每輪中的 function() 都返回并釋放了棧幀空間，因此空間復(fù)雜度仍為 O(1) 。
• 遞歸函數(shù) recur() 在運行過程中會同時存在 n 個未返回的 recur() ，從而占用 O(n) 的棧幀空間。

int func() {
    // 執(zhí)行某些操作
    return 0;
}
/* 循環(huán) O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        func();
    }
}
/* 遞歸 O(n) */
void recur(int n) {
    if (n == 1) return;
    return recur(n - 1);
}

常見類型

設(shè)輸入數(shù)據(jù)大小為 n ，圖 2-16 展示了常見的空間復(fù)雜度類型（從低到高排列）。

圖 2-16   常見的空間復(fù)雜度類型

1.   常數(shù)階 O(1)

常數(shù)階常見于數(shù)量與輸入數(shù)據(jù)大小 n 無關(guān)的常量、變量、對象。

需要注意的是，在循環(huán)中初始化變量或調(diào)用函數(shù)而占用的內(nèi)存，在進入下一循環(huán)后就會被釋放，因此不會累積占用空間，空間復(fù)雜度仍為 O(1) ：

space_complexity.cpp

/* 函數(shù) */
int func() {
    // 執(zhí)行某些操作
    return 0;
}

/* 常數(shù)階 */
void constant(int n) {
    // 常量、變量、對象占用 O(1) 空間
    const int a = 0;
    int b = 0;
    vector<int> nums(10000);
    ListNode node(0);
    // 循環(huán)中的變量占用 O(1) 空間
    for (int i = 0; i < n; i++) {
        int c = 0;
    }
    // 循環(huán)中的函數(shù)占用 O(1) 空間
    for (int i = 0; i < n; i++) {
        func();
    }
}

 線性階 O(n)

線性階常見于元素數(shù)量與 n 成正比的數(shù)組、鏈表、棧、隊列等：

space_complexity.cpp

/* 線性階 */
void linear(int n) {
    // 長度為 n 的數(shù)組占用 O(n) 空間
    vector<int> nums(n);
    // 長度為 n 的列表占用 O(n) 空間
    vector<ListNode> nodes;
    for (int i = 0; i < n; i++) {
        nodes.push_back(ListNode(i));
    }
    // 長度為 n 的哈希表占用 O(n) 空間
    unordered_map<int, string> map;
    for (int i = 0; i < n; i++) {
        map[i] = to_string(i);
    }
}

如圖 2-17 所示，此函數(shù)的遞歸深度為 $n$ ，即同時存在 $n$ 個未返回的 linear_recur() 函數(shù)，使用 $O\left(n\right)$ 大小的棧幀空間：

space_complexity.cpp

/* 線性階（遞歸實現(xiàn)） */
void linearRecur(int n) {
    cout << "遞歸 n = " << n << endl;
    if (n == 1)
        return;
    linearRecur(n - 1);
}

圖 2-17   遞歸函數(shù)產(chǎn)生的線性階空間復(fù)雜度

平方階 O(n2)

平方階常見于矩陣和圖，元素數(shù)量與 n 成平方關(guān)系：

space_complexity.cpp

/* 平方階 */
void quadratic(int n) {
    // 二維列表占用 O(n^2) 空間
    vector<vector<int>> numMatrix;
    for (int i = 0; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j < n; j++) {
            tmp.push_back(0);
        }
        numMatrix.push_back(tmp);
    }
}

如圖 2-18 所示，該函數(shù)的遞歸深度為 $n$ ，在每個遞歸函數(shù)中都初始化了一個數(shù)組，長度分別為 $n$、$n?1$、$\dots$、$2$、$1$ ，平均長度為 $n/2$ ，因此總體占用 $O\left(n^2\right)$ 空間：

space_complexity.cpp

/* 平方階（遞歸實現(xiàn)） */
int quadraticRecur(int n) {
    if (n <= 0)
        return 0;
    vector<int> nums(n);
    cout << "遞歸 n = " << n << " 中的 nums 長度 = " << nums.size() << endl;
    return quadraticRecur(n - 1);
}

圖 2-18   遞歸函數(shù)產(chǎn)生的平方階空間復(fù)雜度

指數(shù)階 O(2^n)

指數(shù)階常見于二叉樹。觀察圖 2-19 ，高度為 n 的“滿二叉樹”的節(jié)點數(shù)量為 2n?1 ，占用 O(2^n) 空間：

space_complexity.cpp

/* 指數(shù)階（建立滿二叉樹） */
TreeNode *buildTree(int n) {
    if (n == 0)
        return nullptr;
    TreeNode *root = new TreeNode(0);
    root->left = buildTree(n - 1);
    root->right = buildTree(n - 1);
    return root;
}

圖 2-19   滿二叉樹產(chǎn)生的指數(shù)階空間復(fù)雜度

對數(shù)階 O(log?n)

對數(shù)階常見于分治算法。例如歸并排序，輸入長度為 n 的數(shù)組，每輪遞歸將數(shù)組從中點劃分為兩半，形成高度為 log?n 的遞歸樹，使用 O(log?n) 棧幀空間。

再例如將數(shù)字轉(zhuǎn)化為字符串，輸入一個正整數(shù) n ，它的位數(shù)為 log10 ?n +1 ，即對應(yīng)字符串長度為 log10? n +1 ，因此空間復(fù)雜度為 O(log10 n +1)=O(log? n) 。

權(quán)衡時間與空間

理想情況下，我們希望算法的時間復(fù)雜度和空間復(fù)雜度都能達到最優(yōu)。然而在實際情況中，同時優(yōu)化時間復(fù)雜度和空間復(fù)雜度通常是非常困難的。

降低時間復(fù)雜度通常需要以提升空間復(fù)雜度為代價，反之亦然。我們將犧牲內(nèi)存空間來提升算法運行速度的思路稱為“以空間換時間”；反之，則稱為“以時間換空間”。

選擇哪種思路取決于我們更看重哪個方面。在大多數(shù)情況下，時間比空間更寶貴，因此“以空間換時間”通常是更常用的策略。當然，在數(shù)據(jù)量很大的情況下，控制空間復(fù)雜度也是非常重要的。