时间复杂度和空间复杂度

时间复杂度

衡量算法执行所需的时间，常用大O表示法。

O(1)：常数时间
O(log n)：对数时间
O(n)：线性时间
O(n log n)：线性对数时间
O(n²)：平方时间
O(2ⁿ)：指数时间

空间复杂度

衡量算法执行所需的内存空间。

01-枚举、模拟

枚举算法

逐个尝试所有可能的情况，找到符合条件的解。

// 枚举1~n中的偶数
for(int i = 1; i <= n; i++) {
    if(i % 2 == 0) {
        cout << i << endl;
    }
}

模拟算法

按照题目描述，一步步模拟过程。

02-高精度

高精度加法

vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int carry = 0;
    for(int i = 0; i < a.size() || i < b.size(); i++) {
        if(i < a.size()) carry += a[i];
        if(i < b.size()) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    if(carry) c.push_back(carry);
    return c;
}

高精度乘法

vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    int carry = 0;
    for(int i = 0; i < a.size() || carry; i++) {
        if(i < a.size()) carry += a[i] * b;
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

03-基础排序

冒泡排序

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n-i-1; j++) {
        if(a[j] > a[j+1]) {
            swap(a[j], a[j+1]);
        }
    }
}

选择排序

for(int i = 0; i < n; i++) {
    int min_idx = i;
    for(int j = i+1; j < n; j++) {
        if(a[j] < a[min_idx]) min_idx = j;
    }
    swap(a[i], a[min_idx]);
}

快速排序

void quick_sort(int a[], int l, int r) {
    if(l >= r) return;
    int pivot = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j) {
        do i++; while(a[i] < pivot);
        do j--; while(a[j] > pivot);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j+1, r);
}

04-递推

递推公式

通过已知的前几项，推导出后面的项。

斐波那契数列

f[0] = 0; f[1] = 1;
for(int i = 2; i <= n; i++) {
    f[i] = f[i-1] + f[i-2];
}

递推的应用

组合计数
状态转移
动态规划基础

05-递归

递归概念

函数调用自身，需要有终止条件。

阶乘

int factorial(int n) {
    if(n == 1) return 1;
    return n * factorial(n-1);
}

递归与递推的区别

递推：从已知推未知，正向求解
递归：从未知推已知，逆向求解

06-分治

分治思想

将问题分成若干个子问题，分别求解后合并。

归并排序

void merge_sort(int a[], int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid+1, r);
    // 合并两个有序数组
    int i = l, j = mid+1, k = 0;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(i = l, k = 0; i <= r; i++, k++) a[i] = tmp[k];
}

07-贪心

贪心思想

每次选择当前最优的方案，希望最终得到全局最优。

活动选择问题

选择最多的不重叠活动。

// 按结束时间排序
sort(activities.begin(), activities.end(), 
    [](const Activity& a, const Activity& b) {
        return a.end < b.end;
    });
// 贪心选择
int last_end = -1, count = 0;
for(auto& act : activities) {
    if(act.start >= last_end) {
        count++;
        last_end = act.end;
    }
}

08-前缀和与差分

前缀和

// 一维前缀和
s[i] = s[i-1] + a[i];

// 查询[l, r]区间和
sum = s[r] - s[l-1];

二维前缀和

// 二维前缀和
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];

// 查询(x1,y1)-(x2,y2)矩形和
sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];

差分

// 一维差分
b[l] += c; b[r+1] -= c;

// 还原数组
for(int i = 1; i <= n; i++) {
    b[i] += b[i-1];
}

09-深度优先搜索（DFS）

DFS概念

沿着一条路径走到底，再回溯探索其他路径。

DFS模板

void dfs(int u) {
    visited[u] = true;
    for(int v : adj[u]) {
        if(!visited[v]) {
            dfs(v);
        }
    }
}

DFS应用

连通性问题
排列组合问题
图的遍历

10-广度优先搜索（BFS）

BFS概念

按层次遍历，先访问所有距离相同的节点。

BFS模板

queue<int> q;
q.push(start);
visited[start] = true;

while(!q.empty()) {
    int u = q.front();
    q.pop();
    for(int v : adj[u]) {
        if(!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

BFS应用

最短路径问题
层次遍历
连通性问题

动态规划

动态规划概念

将问题分解为子问题，保存子问题的解，避免重复计算。

动态规划步骤

定义状态
状态转移方程
初始状态
计算顺序

最长上升子序列

// O(n²)解法
for(int i = 1; i <= n; i++) {
    dp[i] = 1;
    for(int j = 1; j < i; j++) {
        if(a[j] < a[i]) {
            dp[i] = max(dp[i], dp[j]+1);
        }
    }
}

背包问题

01背包
完全背包
多重背包