时光荏苒

风铃叮当响(看猴请@)

2026-07-13 14:45:25

发布于：广东

19阅读

0回复

0点赞

关于时间复杂度，想必大家都有了解。在这里，我将详细讲解时间复杂度。

$1.排序$

排序法	最差时间复杂度	平均时间复杂度	最优时间复杂度
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
快速排序	$O(n^2)$	$O(n\log n)$	$O(n \log n)$

冒泡排序代码框架（已优化）

#include <iostream>
#include <vector>
using namespace std;

void bubble_sort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        bool swapped = true;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = false;
            }
        }
        if (swapped) break;
    }
}

插入排序代码框架

void insert_sort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int tmp = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > tmp) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = tmp;
    }
}

选择排序代码框架

void select_sort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        int minpos = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minpos]) minpos = j;
        }
        swap(a[i], a[minpos]);
    }
}

堆排序代码框架（大根堆）

void heapify(vector<int>& a, int n, int root) {
    int largest = root;
    int l = root * 2 + 1;
    int r = root * 2 + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != root) {
        swap(a[root], a[largest]);
        heapify(a, n, largest);
    }
}

void heap_sort(vector<int>& a) {
    int n = a.size();
    // 建堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);
    // 弹出堆顶
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        heapify(a, i, 0);
    }
}

归并排序代码框架

void merge(vector<int>& a, int l, int mid, int r) {
    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else tmp.push_back(a[j++]);
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = 0; k < tmp.size(); k++)
        a[l + k] = tmp[k];
}

void merge_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    merge(a, l, mid, r);
}

快速排序代码框架

#include <cstdlib>
#include <ctime>
int partition(vector<int>& a, int l, int r) {
    // 随机选基准防退化
    srand((unsigned)time(NULL));
    int randp = l + rand() % (r - l + 1);
    swap(a[randp], a[r]);
    int pivot = a[r];
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) swap(a[++i], a[j]);
    }
    swap(a[i + 1], a[r]);
    return i + 1;
}

void quick_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int pos = partition(a, l, r);
    quick_sort(a, l, pos - 1);
    quick_sort(a, pos + 1, r);
}

$2.质数$

判断类型	判断方法	最差时间复杂度	平均时间复杂度	最优时间复杂度	核心限制
单个数字	朴素试除法	$O(n)$	$O(n)$	$O(1)$ （ $n=$ 偶数时）	无
	基础优化试除法	$O(\sqrt n)$	$O(\sqrt n)$	$O(1)$ （ $n=$ 偶数时）
	Miller-Rabin	$O(\log^3 n)$	$O(\log^3 n)$	$O(\log^3 n)$
区间数字	设区间为 $[A,B]$ ，长度 $L=B-A+1$
	埃氏筛	$O(B\log \log B)$			$B$ 不能太大，无法求远端区间
	线性欧拉筛	$O(B)$			$B$ 不能太大，无法求远端区间
	分段区间筛	$O(L\log \log B)$			$B-A$ 不超过 $10^6\sim10^7$

【单个数字】基础优化试除法代码框架

#include <iostream>
#include <cmath>
using namespace std;

// 判断 n 是否为质数
bool isPrime_brute(long long n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    // 只枚举奇数到 sqrt(n)
    long long lim = sqrt(n);
    for (long long i = 3; i <= lim; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

【单个数字】Miller-Rabin代码框架

typedef long long ll;
ll mul(ll a, ll b, ll mod) {
    return (__int128)a * b % mod;
}
ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = mul(res, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return res;
}
bool MR(ll n, ll a) {
    ll d = n - 1, r = 0;
    while (d % 2 == 0) d /= 2, r++;
    ll x = qpow(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (ll i = 1; i < r; i++) {
        x = mul(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}
// 对 2^64 以内数字完全正确，无需随机
bool isPrime_MR(ll n) {
    if (n <= 1) return false;
    int base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (int a : base) {
        if (n == a) return true;
        if (n % a == 0) return false;
        if (!MR(n, a)) return false;
    }
    return true;
}

【区间数字】埃氏筛代码框架

#include <vector>
using namespace std;

// 筛出 [0, n] 所有数字是否为质数，返回标记数组
vector<bool> sieveErato(int n)
{
    vector<bool> isP(n + 1, true);
    isP[0] = isP[1] = false; // 0、1不是质数
    for (int i = 2; 1LL * i * i <= n; ++i)
    {
        if (isP[i]) // i是质数，标记它所有倍数
        {
            for (int j = i * i; j <= n; j += i)
            {
                isP[j] = false;
            }
        }
    }
    return isP;
}
}

【区间数字】欧拉线性筛代码框架

vector<bool> sieve_euler(int n) {
    vector<bool> isp(n + 1, true);
    vector<int> primes;
    isp[0] = isp[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isp[i]) primes.push_back(i);
        for (int p : primes) {
            if (1LL * i * p > n) break;
            isp[i * p] = false;
            if (i % p == 0) break;
        }
    }
    return isp;
}

【区间数字】分段区间筛

#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

// 输入区间 [L, R]，返回区间内素数数量/标记数组
vector<bool> segment_sieve(ll L, ll R) {
    ll sqrtR = sqrt(R);
    // 第一步：筛出 1~sqrt(R) 所有小质数
    vector<bool> small(sqrtR + 1, true);
    vector<ll> p;
    small[0] = small[1] = false;
    for (ll i = 2; i <= sqrtR; i++) {
        if (small[i]) {
            p.push_back(i);
            for (ll j = i * i; j <= sqrtR; j += i)
                small[j] = false;
        }
    }
    // 第二步：初始化区间标记
    ll len = R - L + 1;
    vector<bool> seg(len, true);
    if (L == 1) seg[0] = false; // 1不是质数
    // 用每个小质数标记区间内倍数
    for (ll prime : p) {
        // 找到 >= L 的第一个 prime 倍数
        ll start = max(prime * prime, ((L + prime - 1) / prime) * prime);
        for (ll j = start; j <= R; j += prime) {
            seg[j - L] = false;
        }
    }
    return seg;
}

$3.DP$

DP类型	时间复杂度	提示
01 背包 / 完全背包	$O(nV)$	$n$ 件物品，容量 $V$
LIS 朴素	$O(n^2)$
LIS 贪心二分	$O(n\log n)$
LCS	$O(nm)$	两串长度 $n,m$
区间 DP（石子合并）	$O(n^3)$	长度为 $n$
数字三角形	$O(n^2)$	设层数为 $n$

$01$ 背包代码框架

#include <iostream>
#include <vector>
using namespace std;
const int MAXV = 1005;
int dp[MAXV];

int main()
{
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
    {
        int w, v;
        cin >> w >> v;
        // 倒序，防止重复选取
        for (int j = V; j >= w; j--)
        {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

完全背包代码框架

#include <iostream>
#include <vector>
using namespace std;
int dp[1005];

int main()
{
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
    {
        int w, v;
        cin >> w >> v;
        // 正序，可重复取
        for (int j = w; j <= V; j++)
        {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

LIS优化版

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), st;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int x : a)
    {
        auto it = lower_bound(st.begin(), st.end(), x);
        if (it == st.end()) st.push_back(x);
        else *it = x;
    }
    cout << st.size() << endl;
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

区间DP

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), sum(n + 1, 0);
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        dp[i][i] = 0; // 单堆代价0
    }
    // len：区间长度
    for (int len = 2; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            for (int mid = l; mid < r; mid++)
            {
                dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r] + sum[r] - sum[l - 1]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

数字三角形代码框架

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> tri(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> tri[i][j];
    // 自底向上
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            tri[i][j] += max(tri[i + 1][j], tri[i + 1][j + 1]);
        }
    }
    cout << tri[1][1] << endl;
    return 0;
}