第10章 时间复杂度进阶

// 判断一个函数是否确实是某上界（教学直觉示例）
#include <iostream>
using namespace std;

// f 与 g 在 n 较大时的比值，若 f/g 有界则 f = O(g)
bool isBigO(double f(int), double g(int), int N = 1000) {
    double mx = 0;
    for (int n = 1; n <= N; ++n) {
        double r = f(n) / g(n);
        if (r > mx) mx = r;
    }
    return mx < 1e9;   // 比值有上界即认为 f = O(g)
}

double f1(int n) { return 2.0 * n * n + 3.0 * n; }
double g1(int n) { return 1.0 * n * n; }

int main() {
    cout << (isBigO(f1, g1) ? "2n^2+3n = O(n^2)\n" : "no\n");  // 输出成立
    return 0;
}

// 数一数各层循环的实际复杂度（教学示例）
#include <iostream>
using namespace std;

int countWork(int n) {
    long long ops = 0;
    for (int i = 1; i <= n; ++i)            // O(n)
        for (int j = i; j <= n; j += i)     // 内层约 n/i 次，总 Σ n/i = n·H(n) ≈ n log n
            ++ops;
    return ops;   // 该双重循环整体为 O(n log n)，而非 O(n^2)
}

int main() {
    for (int n : {100, 1000, 10000})
        cout << "n=" << n << " 运算次数≈" << countWork(n) << "\n";
    return 0;
}

// 线性查找的最好/最坏/平均（教学示例）
#include <iostream>
using namespace std;

// 在 a[0..n-1] 中找 x，返回下标或 -1
int linearSearch(int a[], int n, int x) {
    for (int i = 0; i < n; ++i) {     // 最好: 第1个就中 O(1); 最坏: 扫完 O(n)
        if (a[i] == x) return i;
    }
    return -1;                          // 平均比较次数 (n+1)/2 = O(n)
}

// 递归树思想落到代码：归并排序的递归结构（教学示例）
#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> t(r - l + 1);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) t[k++] = (a[i] <= a[j] ? a[i++] : a[j++]);
    while (i <= m) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    for (int p = 0; p < k; ++p) a[l + p] = t[p];
}

void mergeSort(vector<int>& a, int l, int r) {   // T(n) = 2T(n/2) + O(n)
    if (l >= r) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

int main() {
    vector<int> a = {5, 2, 4, 6, 1, 3};
    mergeSort(a, 0, a.size() - 1);
    for (int v : a) cout << v << " ";   // 1 2 3 4 5 6
    cout << "\n";
    return 0;
}

// 主定理情形判定器（教学示例：输入 a,b 及 f(n) 的级别，输出属于哪类）
#include <iostream>
#include <cmath>
using namespace std;

// level: 0=常数, 1=log, 2=n, 3=nlogn, 4=n^2 ... 这里只演示关键三种
string master(int a, int b, double nlogba) {
    // nlogba = log_b(a) 已知时直接传，避免浮点误差
    if (nlogba > 1.0)      return "情形1为主: T(n)=Theta(n^{log_b a})";
    if (fabs(nlogba - 1.0) < 1e-9) return "情形2: T(n)=Theta(n^{log_b a} * log n)";
    return "需比较 f(n) 与 n^{log_b a}";
}

int main() {
    cout << "归并 a=2,b=2,log2(2)=1 -> " << master(2, 2, 1.0) << "\n";  // 情形2
    cout << "Strassen a=7,b=2,log2(7)=2.81 -> " << master(7, 2, log2(7)) << "\n"; // 情形1
    return 0;
}

// 模拟动态数组翻倍扩容，验证总拷贝量 O(n)（教学示例）
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a;
    long long copies = 0;
    int cap = 0;        // 当前容量
    for (int i = 1; i <= 16; ++i) {
        if ((int)a.size() == cap) {        // 满了，翻倍
            int ncap = cap ? cap * 2 : 1;
            copies += a.size();            // 复制旧元素
            cap = ncap;
        }
        a.push_back(i);
    }
    cout << "插入16个，扩容拷贝总次数=" << copies << " (<=2n)\n";  // 1+2+4+8=15
    return 0;
}

// 栈的多操作（multipop）均摊 O(1)（教学示例）
#include <iostream>
#include <vector>
using namespace std;

struct Stack {
    vector<int> s;
    void push(int x) { s.push_back(x); }
    void pop() { if (!s.empty()) s.pop_back(); }
    void multipop(int k) { while (k-- && !s.empty()) s.pop_back(); }  // 单次最坏 O(n)
};

int main() {
    Stack st;
    for (int i = 0; i < 5; ++i) st.push(i);
    st.multipop(3);   // 弹 3 个
    st.push(9);
    st.multipop(10);  // 一次弹空，但总 pop 数仍受 push 数限制
    cout << "剩余大小=" << st.s.size() << "\n";  // 0
    return 0;
}

// 路径压缩使 find 均摊 O(alpha(n))（教学示例，呼应第9章）
#include <iostream>
#include <vector>
using namespace std;

struct DSU {
    vector<int> fa;
    DSU(int n) : fa(n + 1) { for (int i = 1; i <= n; ++i) fa[i] = i; }
    int find(int x) {                       // 路径压缩：把沿途父指针直接指向根
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void unite(int x, int y) { fa[find(x)] = find(y); }
};

int main() {
    DSU d(6);
    d.unite(1, 2); d.unite(2, 3); d.unite(4, 5);
    cout << "1 与 3 同根? " << (d.find(1) == d.find(3) ? "是" : "否") << "\n";  // 是
    return 0;
}

// 实测每秒可执行的简单运算量（教学示例，用于估算 n 上界）
#include <iostream>
#include <chrono>
using namespace std;

int main() {
    const int N = 100000000;   // 1e8
    auto t0 = chrono::high_resolution_clock::now();
    long long s = 0;
    for (int i = 0; i < N; ++i) s += i;
    auto t1 = chrono::high_resolution_clock::now();
    double sec = chrono::duration<double>(t1 - t0).count();
    cout << "1e8 次加法耗时 " << sec << " 秒，约 " << (long long)(N / sec) << " ops/s\n";
    return 0;
}