时间/空间复杂度

算法（Algorithm）

算法是解决问题的一种方法，由一系列的步骤组成。算法有 5 个特点：

1. 有穷性（finiteness）：算法必须在有限个步骤后终止。
2. 确定性（definiteness）：算法的每个步骤必须有确切的定义。
3. 输入项（input）：一个算法有 0 个或多个输入。
4. 输出项（output）：一个算法有 1 个或多个输出，没有输出的算法是毫无意义的。
5. 可行性（effectiveness）：算法中执行的任何步骤都可以被分解为基本的可执行操作。

时间复杂度（Time Complexity）

算法有高效的，也有拙劣的。衡量算法好坏的标准有时间复杂度和空间复杂度。

想象一个场景：老板让小灰和大黄完成一个需求，两人都完成并交付了各自的代码，代码的功能是一样的。但是，大黄的代码运行一次要花 100ms，占用 5MB 内存；小灰的代码运行一次要花 100s，占用 500MB 内存。

“小灰，收拾东西走人，明天不用来上班了！”

小灰虽然也按照老板的要求实现了功能，但他的代码存在很严重的问题：运行时间长、占用空间大。

算法的时间复杂度是指算法中基本运算的执行次数，其中基本运算指的是加减法、交换、比较等操作。

算法的效率应该取决于算法本身，与机器无关。分析算法运行效率时应该考虑的是运行时间与输入规模之间的关系。通过计算算法中基本运算的执行次数，可以得到一个关于输入规模 $n$ 的函数。

时间复杂度一般采用大 O 表示法，表示算法的运行时间与输入规模之间的增长关系。常见的时间复杂度包括 $O(1)$、$O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$、$O(2^n)$、$O(n!)$ 等。

时间复杂度需要满足以下原则：

1. 如果运行时间是常量级，则用 $O(1)$ 表示。
2. 只保留时间函数中的最高阶项。
3. 如果最高阶项存在，则省去最高阶项前的系数。

大 O 符号

大 O 符号用于表示时间复杂度的上界（最坏情况），即算法的阶不会超过大 O 符号中的函数 $g(n)$。

大 $\Omega$ 符号

大 $\Omega$ 符号用于表示时间复杂度的下界（最好情况），即算法的阶不会低于大 $\Omega$ 符号中的函数 $g(n)$。

小 o 符号

小 o 符号用于表示时间复杂度的上界，即算法的阶一定低于小 o 符号中的函数 $g(n)$。

小 $\omega$ 符号

小 $\omega$ 符号用于表示时间复杂度的下界，即算法的阶一定高于小 $\omega$ 符号中的函数 $g(n)$。

$\Theta$ 符号

若 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$，则称 $f(n)$ 的阶与 $g(n)$ 的阶相等：

百钱买百鸡

公鸡 5 文钱 1 只，母鸡 3 文钱 1 只，小鸡 1 文钱 3 只，如果用 100 文钱买 100 只鸡，那么公鸡、母鸡和小鸡各应该买多少只？

#include <stdio.h>

void buy(int n, int money) {
    for (int x = 0; x <= n / 5; x++) {
        for (int y = 0; y <= n / 3; y++) {
            int z = n - x - y;
            if (z > 0 && z % 3 == 0 && 5 * x + 3 * y + z / 3 == money) {
                printf("x = %d, y = %d, z = %d\n", x, y, z);
            }
        }
    }
}

int main() {
    buy(100, 100);
    return 0;
}

空间复杂度（Space Complexity）

算法占用的内存空间自然是越小越好，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大 O 表示法。

正所谓鱼和熊掌不可兼得，很多时候不得不在时间复杂度和空间复杂度之间进行取舍。绝大多数时候，时间复杂度更为重要，宁可多分配一些内存空间，也要提升程序的执行速度。

均摊时间复杂度（Amortized Time Complexity）

均摊时间复杂度用于分析一组操作中，虽然某个操作的时间复杂度很高，但是经过若干次操作后，这组操作的平均时间复杂度较低的情况。

动态数组

void add(DynamicArray *list, int element) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->arr = realloc(list->arr, list->capacity * sizeof(int));
    }
    list->arr[list->size++] = element;
}

这段代码实现了往数组中添加数据的功能。在数组没有满的情况下，直接将数据添加到数组末尾，时间复杂度为 $O(1)$。

但是当数组已满时，需要创建一个更大的数组，将原数组中的数据复制到新数组中，然后再将新数据添加到数组的末尾，这个过程的时间复杂度为 $O(n)$。

假设数组的容量为 $n$，每执行 $n$ 次 add() 操作，才会进行一次扩容。那么，可以将这一次的 $O(n)$ 的时间均摊到前面的 $n$ 次操作中，这样 add() 操作的均摊时间复杂度就是 $O(1)$。