hello algorithm chapter 2 / space complexity

Overview

space-complexity

Difinition：算法占用内存空间随着输入数据量变大时的增长趋势

输入空间

暂存空间

暂存数据

栈帧空间

指令空间（ignored）

输出空间

Deductive Method

最糟糕的输入：以最差输入数据为准

运行峰值：以算法运行中的峰值内存为准

注意统计栈帧空间

Common types

Constant order

暂存数据：数量与输入数据大小 n 无关的常量、变量、对象。

栈帧空间：循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为O(1)

Linear order

暂存数据：元素数量与n成正比的数组、链表、栈、队列等。

栈帧空间：此函数的递归深度为n，即同时存在n个未返回的 linear_recur() 函数，使用 O(n) 大小的栈帧空间。

Square order

暂存数据：平方阶常见于矩阵和图，元素数量与n成平方关系。

栈帧空间：递归结构+数组

Exponential order

暂存数据：指数阶常见于二叉树。观察图 2-19 ，高度为 \(n\) 的“满二叉树”的节点数量为 \(2^n−1\)，占用 \(O(2^n)\) 空间。

栈帧空间

Logarithmic order

暂存数据

栈帧空间：对数阶常见于分治算法。例如归并排序，输入长度为 n 的数组，每轮递归将数组从中点划分为两半，形成高度为 log⁡n 的递归树，使用 n(log⁡n) 栈帧空间。

Definition

算法占用内存空间随着输入数据量变大时的增长趋势

/* 类 */
class Node {
    int val;
    Node next;
    Node(int x) { val = x; }
}

/* 函数 */
int function() {
    // 执行某些操作...
    return 0;
}

int algorithm(int n) {        // 输入数据
    final int a = 0;          // 暂存数据（常量）
    int b = 0;                // 暂存数据（变量）
    Node node = new Node(0);  // 暂存数据（对象）
    int c = function();       // 栈帧空间（调用函数）
    return a + b + c;         // 输出数据
}

Deductive Method

只关注最差空间复杂度。这是因为内存空间是一项硬性要求。

以最差输入数据为准。如果输入范围是1-10000，那就以10000为考虑输入。
以算法运行中的峰值内存为准。程序在执行最后一行之前，占用 \(O(1)\) 空间；当初始化数组 nums 时，程序占用 \(O(n)\) 空间；因此最差空间复杂度为 \(O(n)\)。

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

在递归函数中，需要注意统计栈帧空间。例如:
函数 loop() 在循环中调用了 n 次 function() ，每轮中的 function() 都返回并释放了栈帧空间，因此空间复杂度仍为 \(O(1)\)。
递归函数 recur() 在运行过程中会同时存在 \(n\) 个未返回的 recur() ，从而占用 \(O(n)\) 的栈帧空间。

int function() {
    // 执行某些操作
    return 0;
}
/* 循环 O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        function();
    }
}
/* 递归 O(n) */
void recur(int n) {
    if (n == 1) return;
    return recur(n - 1);
}

Common types

\(O(1) < O(log n) < O(n) < O(n^2) < O(2^n)\)

Constant order

数量与输入数据大小 \(n\) 无关的常量、变量、对象。

循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为\(O(1)\)。

/* 线性阶 */
void linear(int n) {
    // 长度为 n 的数组占用 O(n) 空间
    int[] nums = new int[n];
    // 长度为 n 的列表占用 O(n) 空间
    List<ListNode> nodes = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        nodes.add(new ListNode(i));
    }
    // 长度为 n 的哈希表占用 O(n) 空间
    Map<Integer, String> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.put(i, String.valueOf(i));
    }
}

/* 线性阶（递归实现） */
void linearRecur(int n) {
    System.out.println("递归 n = " + n);
    if (n == 1)
        return;
    linearRecur(n - 1);
}

Square order

平方阶常见于矩阵和图，元素数量与 \(n\) 成平方关系。

/* 平方阶 */
void quadratic(int n) {
    // 矩阵占用 O(n^2) 空间
    int[][] numMatrix = new int[n][n];
    // 二维列表占用 O(n^2) 空间
    List<List<Integer>> numList = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<Integer> tmp = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            tmp.add(0);
        }
        numList.add(tmp);
    }
}

该函数的递归深度为 \(n\) ，在每个递归函数中都初始化了一个数组，长度分别为 \(n\)、\(n−1\)、…、\(2\)、\(1\)，平均长度为 \(n/2\) ，因此总体占用 \(O(n^2)\) 空间：

/* 平方阶（递归实现） */
int quadraticRecur(int n) {
    if (n <= 0)
        return 0;
    // 数组 nums 长度为 n, n-1, ..., 2, 1
    int[] nums = new int[n];
    System.out.println("递归 n = " + n + " 中的 nums 长度 = " + nums.length);
    return quadraticRecur(n - 1);
}

Exponential order

指数阶常见于二叉树。观察下图，高度为 \(n\) 的“满二叉树”的节点数量为 \(2^n - 1\)，占用 \(O(2^n)\) 空间。

/* 指数阶（建立满二叉树） */
TreeNode buildTree(int n) {
    if (n == 0)
        return null;
    TreeNode root = new TreeNode(0);
    root.left = buildTree(n - 1);
    root.right = buildTree(n - 1);
    return root;
}