算法基础

    一、算法复杂度分析

    熟悉常见复杂度量级：O(1)、O(log n)、O(n)、O(n log n)、O(n²)。

    1. 时间复杂度

    判题机大约 1 秒执行 1e8 次运算。

    // O(1)
int a, b;
cin >> a >> b;
if (a > b) {
}

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

// O(n^2)
for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
    }
}

// O(nm)
for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
    }
}

    2. 空间复杂度

    常见空间复杂度：O(1)、O(n)、O(n²) 等。

    • O(1)：只使用常数个变量。
    • O(n)：使用长度为 n 的数组。
    • O(n²)：使用二维数组等。

    二、递推算法

    递推：在给定初始条件下，已知前一项或前几项求后一项的过程。

    斐波那契数列递推

    // 递推法
long long fib[100] = {0, 1, 1}; // 第 1 项和第 2 项为 1
for (int i = 3; i <= 92; i++) { // 从第 3 项开始递推
    fib[i] = fib[i - 1] + fib[i - 2]; // 递推式
}

// 迭代法
long long a = 1, b = 1, c;
for (int i = 1; i <= 92; i++) {
    c = a + b; // 保存中间状态
    a = b;
    b = c;
}