complexity_adt.cpp

  // ============================================================
//     程序复杂度分析 & 抽象数据类型（ADT）—— 数据结构理论基础
// ============================================================
//
// 【第一部分：程序复杂度（Program Complexity）】
//
//   复杂度分析是算法和数据结构最重要的评价标准。它回答两个问题：
//     - 时间：随着输入规模 n 的增长，程序运行时间的增长速率是多少？
//     - 空间：随着 n 的增长，程序占用内存的增长速率是多少？
//
//   我们通常关心的是"增长率"（growth rate），而非精确的秒数/字节数，
//   因为精确值依赖于硬件、编译器优化等因素，而增长率是算法本身的性质。
//
// ┌─────────────────────────────────────────────────────────────┐
// │                     三大渐进符号                             │
// ├─────────────────────────────────────────────────────────────┤
// │  O (Big-Oh)   上界 / 最坏情况  f(n) = O(g(n))              │
// │                存在 c>0, n₀ 使得 n≥n₀ 时 f(n) ≤ c·g(n)     │
// │                含义：增长不会比 g(n) 更快                    │
// │                                                             │
// │  Ω (Omega)    下界 / 最好情况  f(n) = Ω(g(n))              │
// │                存在 c>0, n₀ 使得 n≥n₀ 时 f(n) ≥ c·g(n)     │
// │                含义：增长至少和 g(n) 一样快                  │
// │                                                             │
// │  Θ (Theta)    紧确界          f(n) = Θ(g(n))               │
// │                同时满足 O(g(n)) 和 Ω(g(n))                  │
// │                含义：增长速率恰好和 g(n) 同阶               │
// │                                                             │
// │  示例：插入排序对一个乱序数组                                │
// │    最好  Θ(n)       —— 数组已有序，每次只比 1 次            │
// │    最坏  Θ(n²)      —— 数组逆序，每次比 i 次               │
// │    平均  Θ(n²)      —— 平均比 i/2 次                       │
// │    → 我们说"插入排序的时间复杂度是 O(n²)"                    │
// │      这里的 O 表示最坏情况上界                               │
// └─────────────────────────────────────────────────────────────┘
//
// 【常见复杂度阶级（从快到慢）】
//
//   O(1)      常量时间     Hash 表查找、数组下标访问
//   O(log n)  对数时间     二分查找、平衡树查找
//   O(n)      线性时间     遍历数组、计数排序
//   O(n log n)线性对数时间  归并排序、堆排序、快速排序(平均)
//   O(n²)     平方时间     插入/冒泡/选择排序
//   O(n³)     立方时间     朴素矩阵乘法
//   O(2ⁿ)     指数时间     暴力枚举子集、斐波那契(递归)
//   O(n!)     阶乘时间     暴力旅行商问题
//
//   ┌──────────────────────────────────────────┐
//   │  增长率对比（n=100 时各阶的量级）         │
//   │                                          │
//   │  O(1)      → 1                           │
//   │  O(log n)  → ≈7                          │
//   │  O(n)      → 100                         │
//   │  O(n log n)→ ≈700                        │
//   │  O(n²)     → 10,000                      │
//   │  O(2ⁿ)     → 1.27×10³⁰  (宇宙年龄级别!)  │
//   │  O(n!)     → 9.33×10¹⁵⁷ (完全不可行)     │
//   └──────────────────────────────────────────┘
//
// 【如何分析一段代码的复杂度？】
//
//   规则 1（顺序结构）：取最大的
//     O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
//     例：O(n²) + O(n) = O(n²)
//
//   规则 2（循环结构）：乘法
//     外层 O(n) × 内层 O(n) = O(n²)
//
//   规则 3（if-else）：取最大的分支
//     O(max(if分支, else分支))
//
//   规则 4（递归）：用递归树 / 主定理
//     T(n) = a·T(n/b) + f(n)
//
//   规则 5（对数循环）：
//     for (int i=1; i<n; i*=2)  → O(log n)
//     for (int i=n; i>0; i/=2)  → O(log n)
//
// ┌─────────────────────────────────────────────────────────────┐
// │                    对数循环示例分析                          │
// │                                                             │
// │  for (int i = 1; i < n; i *= 2)        // O(log n)         │
// │      cout << i;                                            │
// │                                                             │
// │  为什么是 O(log n)？                                        │
// │    i 的取值: 1, 2, 4, 8, 16, ..., 2^k                      │
// │    设 2^k ≥ n 时停止，即 k ≥ log₂ n                        │
// │    循环次数 = k = ⌈log₂ n⌉                                 │
// │                                                             │
// │  for (int i = 1; i < n; i *= 2)        // O(n log n)       │
// │      for (int j = 0; j < n; j++)                           │
// │          cout << i * j;                                    │
// │                                                             │
// │  外层 O(log n)，内层 O(n)，总复杂度 O(n log n)              │
// └─────────────────────────────────────────────────────────────┘
//
// 【主定理（Master Theorem）—— 递归的万能公式】
//
//   对于 T(n) = a·T(n/b) + f(n)，其中 a≥1, b>1：
//
//   情况 1: f(n) = O(n^{log_b a - ε}) → T(n) = Θ(n^{log_b a})
//   情况 2: f(n) = Θ(n^{log_b a})      → T(n) = Θ(n^{log_b a} log n)
//   情况 3: f(n) = Ω(n^{log_b a + ε})  → T(n) = Θ(f(n))
//           (且需满足 af(n/b) ≤ cf(n), c<1)
//
//   常见递归的复杂度速查：
//
//   ┌──────────────────────┬──────────┬────────────────────┐
//   │ 递归式               │ 实例     │ 复杂度             │
//   ├──────────────────────┼──────────┼────────────────────┤
//   │ T(n)=2T(n/2)+O(1)    │ 二叉树遍历│ Θ(n)              │
//   │ T(n)=2T(n/2)+O(n)    │ 归并排序  │ Θ(n log n)        │
//   │ T(n)=T(n/2)+O(1)     │ 二分查找  │ Θ(log n)          │
//   │ T(n)=T(n-1)+O(1)     │ 线性递归  │ Θ(n)              │
//   │ T(n)=2T(n-1)+O(1)    │ 汉诺塔    │ Θ(2ⁿ)             │
//   │ T(n)=T(n/b)+O(1)     │ 一个子问题│ Θ(log n)          │
//   └──────────────────────┴──────────┴────────────────────┘
//
// 【空间复杂度】
//
//   空间复杂度衡量算法运行所需的额外内存（不包括输入本身）。
//
//   常见情况：
//     O(1)    原地算法   冒泡排序、插入排序、堆排序
//     O(log n)递归栈     快速排序（递归栈深度）
//     O(n)    额外数组   归并排序的临时数组
//     O(n²)   矩阵       DP 表格
//
//   注意：递归的"隐式"空间占用——每次递归调用都需要栈帧！
//   尾递归可以被编译器优化为 O(1)（但 C++ 标准不保证）。
//
// 【逆序对（Inversion）与排序复杂度】
//
//   定义：数组中 i<j 但 arr[i] > arr[j] 的数对 (i, j)
//
//   逆序对的意义：
//     - 完全有序数组：逆序对数 = 0
//     - 完全逆序数组：逆序对数 = n(n-1)/2
//     - 逆序对数 = 将乱序数组排为有序所需的"最少交换次数"
//                  （仅限相邻交换）
//
//   示例：[3, 1, 2] 的逆序对：
//     (3,1): 3>1 且 0<1 ✓
//     (3,2): 3>2 且 0<2 ✓
//     (1,2): 1<2          ✗
//     共 2 个逆序对
//
//   与排序算法的关系：
//     冒泡排序每交换相邻一次消除 1 个逆序对 → 比较+交换次数 = 逆序对数
//     插入排序每次移动消除 1 个逆序对       → O(n+逆序对数)
//     归并排序可以在排序同时 O(n log n) 计算逆序对数
//
// ============================================================
//
// 【第二部分：抽象数据类型（ADT — Abstract Data Type）】
//
//   ADT 是数据结构的"接口规范"，定义了一组值和一组操作，
//   但不规定具体实现方式。
//
//   ADT 的规范写法包含三个部分：
//     1. 值的定义（Value Definition）
//     2. 操作的定义（Operation Definition）
//     3. 可选的条件（Condition / Constraint）
//
//   每个操作的定义包含：
//     ① 函数头部（signature）：操作名(参数列表) → 返回值
//     ② 前置条件（precondition）：调用前必须满足的条件
//     ③ 后置条件（postcondition）：调用后保证成立的条件
//
// ┌─────────────────────────────────────────────────────────────┐
// │              ADT 示例 1：栈（Stack）                        │
// ├─────────────────────────────────────────────────────────────┤
// │                                                             │
// │  值定义：                                                   │
// │    Stack = 一个线性有序的元素序列 (a₁, a₂, ..., aₙ)        │
// │    其中 a₁ 是栈底，aₙ 是栈顶                                │
// │    约束：只能在栈顶插入和删除（LIFO）                       │
// │                                                             │
// │  操作定义：                                                 │
// │                                                             │
// │    IsEmpty() → bool                                        │
// │      pre:  none                                            │
// │      post: 返回 true 当且仅当 栈中没有元素                  │
// │                                                             │
// │    IsFull() → bool                                         │
// │      pre:  none                                            │
// │      post: 返回 true 当且仅当 栈已满（仅定长数组有）        │
// │                                                             │
// │    Push(item)                                               │
// │      pre:  IsFull() = false                                │
// │      post: item 被添加到栈顶，成为新的 aₙ                   │
// │                                                             │
// │    Pop() → item                                             │
// │      pre:  IsEmpty() = false                               │
// │      post: 栈顶元素 aₙ 被移除并返回                         │
// │                                                             │
// │    Top() → item                                             │
// │      pre:  IsEmpty() = false                               │
// │      post: 返回栈顶元素 aₙ（不删除）                        │
// │                                                             │
// └─────────────────────────────────────────────────────────────┘
//
// ┌─────────────────────────────────────────────────────────────┐
// │              ADT 示例 2：队列（Queue）                      │
// ├─────────────────────────────────────────────────────────────┤
// │                                                             │
// │  值定义：                                                   │
// │    Queue = 一个线性有序的元素序列 (a₁, a₂, ..., aₙ)        │
// │    其中 a₁ 是队头（front），aₙ 是队尾（rear）              │
// │    约束：只能在队头删除，队尾插入（FIFO）                   │
// │                                                             │
// │  操作定义：                                                 │
// │                                                             │
// │    IsEmpty() → bool                                        │
// │    IsFull() → bool                                         │
// │                                                             │
// │    Enqueue(item)                                            │
// │      pre:  IsFull() = false                                │
// │      post: item 被添加到队尾，成为新的 aₙ                   │
// │                                                             │
// │    Dequeue() → item                                         │
// │      pre:  IsEmpty() = false                               │
// │      post: 队头元素 a₁ 被移除并返回                         │
// │                                                             │
// │    Front() → item                                           │
// │      pre:  IsEmpty() = false                               │
// │      post: 返回队头元素 a₁（不删除）                        │
// │                                                             │
// └─────────────────────────────────────────────────────────────┘
//
// ┌─────────────────────────────────────────────────────────────┐
// │         ADT 示例 3：二叉搜索树（BST）                       │
// ├─────────────────────────────────────────────────────────────┤
// │                                                             │
// │  值定义：                                                   │
// │    BST = 一棵二叉树，满足：对于任意节点 v                   │
// │      v 左子树中所有节点的值 < v 的值                        │
// │      v 右子树中所有节点的值 > v 的值                        │
// │    （通常假设没有重复值）                                    │
// │                                                             │
// │  操作定义：                                                 │
// │                                                             │
// │    Search(k) → node | null                                  │
// │      pre:  none                                            │
// │      post: 返回值为 k 的节点，不存在则返回 null             │
// │                                                             │
// │    Insert(k)                                                │
// │      pre:  k 不在树中                                      │
// │      post: 包含 k 的新节点被插入到正确位置，BST 性质保持     │
// │                                                             │
// │    Delete(k)                                                │
// │      pre:  k 在树中                                        │
// │      post: 值为 k 的节点被移除，BST 性质保持                │
// │                                                             │
// │    Inorder() → list                                         │
// │      pre:  none                                            │
// │      post: 返回所有值按升序排列的列表                        │
// │                                                             │
// └─────────────────────────────────────────────────────────────┘
//
// ┌─────────────────────────────────────────────────────────────┐
// │       ADT 示例 4：并查集（Disjoint Set / Union-Find）       │
// ├─────────────────────────────────────────────────────────────┤
// │                                                             │
// │  值定义：                                                   │
// │    DisjointSet = 若干互不相交的集合的集合                     │
// │    （partition / 划分）                                     │
// │    每个集合有一个代表元素（representative）                  │
// │    等价关系：自反性 + 对称性 + 传递性                       │
// │                                                             │
// │  操作定义：                                                 │
// │                                                             │
// │    MakeSet(x)                                               │
// │      pre:  x 不在任何集合中                                │
// │      post: 创建一个仅包含 x 的新集合，x 为代表元素          │
// │                                                             │
// │    Find(x) → representative                                 │
// │      pre:  x 在某个集合中                                  │
// │      post: 返回 x 所在集合的代表元素                        │
// │                                                             │
// │    Union(x, y)                                              │
// │      pre:  x 和 y 在不同集合中                             │
// │      post: x 和 y 所在的集合被合并为一个                    │
// │            新集合的代表元素是合并前的某个代表元素             │
// │                                                             │
// └─────────────────────────────────────────────────────────────┘
//
// 【ADT 与数据结构的关系】
//
//   ADT（抽象数据类型）        数据结构（Data Structure）
//   ─────────────────────      ─────────────────────────
//   定义 "做什么"（What）       定义 "怎么做"（How）
//   接口/规范                   具体实现
//   与语言无关                  与语言相关
//   不关心性能和存储            关心时间/空间复杂度
//
//   同一个 ADT 可以有多种数据结构实现：
//     Stack ADT → 数组实现 / 链表实现
//     Queue ADT → 循环数组 / 链表 / 双栈
//     Set ADT   → BST / 红黑树 / Hash 表 / 跳表
//     Map ADT   → BST / Hash 表 / Trie
//
//   选择什么实现取决于：
//     - 操作频率（读多 vs 写多）
//     - 内存限制（嵌入式 vs 服务器）
//     - 是否需要有序遍历
//     - 缓存友好性
//     - 实现复杂度
//
// ============================================================

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

// 【阅读地图】
//   先用本文件的循环和递归示例练习“规模 n 增长时，哪一项主导代价”，
//   再阅读 ADT 示例。ADT 注释中的 pre / post 是接口契约，不是实现细节。
//   复盘时始终分开回答两个问题：单次操作最坏代价是多少？连续操作的均摊代价是多少？

// ==================== 复杂度分析辅助函数 ====================

// 计算数组中逆序对的数量（使用归并排序思想，O(n log n)）
long long mergeAndCount(vector<int>& arr, vector<int>& temp,
                         int left, int mid, int right)
{
    int i = left;      // 左半起点
    int j = mid + 1;   // 右半起点
    int k = left;      // temp 数组起点
    long long invCount = 0;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            // arr[i] > arr[j] → 左右各剩的元素都构成逆序对
            // 右半元素 arr[j] 比左半 arr[i..mid] 所有元素都小
            temp[k++] = arr[j++];
            invCount += (mid - i + 1);  // ← 关键！
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (i = left; i <= right; i++) arr[i] = temp[i];

    return invCount;
}

long long countInversions(vector<int>& arr, vector<int>& temp,
                           int left, int right)
{
    long long invCount = 0;
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        invCount += countInversions(arr, temp, left, mid);
        invCount += countInversions(arr, temp, mid + 1, right);
        invCount += mergeAndCount(arr, temp, left, mid, right);
    }
    return invCount;
}

long long countInversions(vector<int>& arr)
{
    vector<int> temp(arr.size());
    return countInversions(arr, temp, 0, (int)arr.size() - 1);
}

// ==================== 复杂度演示函数 ====================

// O(1) 常量时间：无论 n 多大，操作次数恒定
int constantTime(vector<int>& arr)
{
    return arr.empty() ? -1 : arr[0];  // 只访问一个元素
}

// O(log n) 对数时间：每次将问题规模减半
int logarithmicTime(vector<int>& arr, int target)
{
    int left = 0, right = (int)arr.size() - 1;
    int steps = 0;
    while (left <= right)
    {
        steps++;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
        {
            cout << "  二分查找步数: " << steps << " (共 " << arr.size()
                 << " 个元素, log₂(n)=" << log2(arr.size()) << ")" << endl;
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    cout << "  二分查找步数: " << steps << endl;
    return -1;
}

// O(n) 线性时间
int linearTime(vector<int>& arr)
{
    int sum = 0;
    for (int x : arr) sum += x;  // 遍历 n 次
    return sum;
}

// O(n²) 平方时间
int quadraticTime(vector<int>& arr)
{
    int count = 0;
    int n = arr.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            count++;  // 执行 n(n-1)/2 次
        }
    }
    return count;
}

// ==================== 主函数 ====================

int main()
{
    cout << "╔══════════════════════════════════════════╗" << endl;
    cout << "║   程序复杂度 & ADT 讲解与演示             ║" << endl;
    cout << "╚══════════════════════════════════════════╝" << endl;

    // ==================== 复杂度演示 ====================
    cout << "\n┌─ 复杂度实际演示 ──────────────────────────┐" << endl;

    int n = 1000000;
    vector<int> bigArr(n);
    for (int i = 0; i < n; i++) bigArr[i] = i;

    cout << "\n>>> O(1) 常量时间" << endl;
    cout << "  数组大小 = " << n << "，取第一个元素: " << constantTime(bigArr) << endl;
    cout << "  无论 n 多大，都是 1 步完成" << endl;

    cout << "\n>>> O(log n) 对数时间（二分查找）" << endl;
    logarithmicTime(bigArr, 777777);

    cout << "\n>>> O(n) 线性时间" << endl;
    cout << "  求 " << n << " 个元素的和，运算次数 = n" << endl;

    cout << "\n>>> O(n²) vs O(n log n) 对比" << endl;
    int sizes[] = {100, 1000, 10000};
    for (int sz : sizes)
    {
        cout << "  n=" << sz << ": n²=" << (long long)sz*sz
             << ", n log n≈" << (long long)(sz * log2(sz)) << endl;
    }
    cout << "  → n=10000 时 n²/n log n ≈ " << (10000.0 / log2(10000))
         << " 倍差距！" << endl;

    // ==================== 逆序对计算 ====================
    cout << "\n>>> 逆序对计算（O(n log n)）" << endl;
    vector<int> demo1 = {8, 4, 2, 1};                                    // 完全逆序
    vector<int> demo2 = {1, 2, 3, 4};                                    // 完全有序
    vector<int> demo3 = {2, 8, 1, 3, 5, 4, 7, 6};                       // 随机

    cout << "  [8,4,2,1] 逆序对数 = " << countInversions(demo1)
         << " (理论最大 = 4×3/2 = 6)" << endl;
    cout << "  [1,2,3,4] 逆序对数 = " << countInversions(demo2)
         << " (完全有序 = 0)" << endl;
    cout << "  [2,8,1,3,5,4,7,6] 逆序对数 = " << countInversions(demo3) << endl;

    // ==================== 主定理验证 ====================
    cout << "\n>>> 主定理验证（归并排序）" << endl;
    cout << "  T(n) = 2T(n/2) + O(n)" << endl;
    cout << "  a=2, b=2, log_b a = 1, f(n)=O(n)" << endl;
    cout << "  f(n) = Θ(n¹) → 情况 2 → T(n) = Θ(n log n)" << endl;

    cout << "\n>>> 主定理验证（二分查找）" << endl;
    cout << "  T(n) = T(n/2) + O(1)" << endl;
    cout << "  a=1, b=2, log_b a = 0, f(n)=O(1)" << endl;
    cout << "  f(n) = Θ(n⁰) = Θ(1) → 情况 2 → T(n) = Θ(log n)" << endl;

    // ==================== 空间复杂度演示 ====================
    cout << "\n>>> 空间复杂度对比" << endl;
    cout << "  冒泡排序:     O(1) — 只需要几个临时变量" << endl;
    cout << "  快速排序:     O(log n) — 递归栈（平均深度）" << endl;
    cout << "  归并排序:     O(n) — 需要长度为 n 的临时数组" << endl;
    cout << "  计数排序:     O(n+k) — n 个输出 + k 个计数槽" << endl;

    cout << "\n复杂度 & ADT 讲解完成！" << endl;
    return 0;
}