时间复杂度：

时间复杂度表示算法运行时间随数据规模增长而增长的趋势。通常用大O表示法表示，记作 O(f(n))，其中 n 是数据规模（比如数组长度、输入大小）

大O表示法的原理

只保留最高次项，忽略常数系数和低次项，因为当 n 很大时，只有最高次项决定增长趋势

• T(n)=3n^2+5n+2 → O(n^2)

• T(n)=1000n → O(n)

• T(n)=2^n+n^2 → O(2^n)

常见时间复杂度及其含义

复杂度	名称	典型场景
O(1)	常数阶	数组按索引访问
O(log⁡(n))	对数阶	二分查找
O(n)	线性阶	遍历数组
O(nlog⁡(n))	线性对数阶	快速排序、归并排序
O(n^2)	平方阶	冒泡排序、选择排序
O(2^n)	指数阶	递归求斐波那契数列（未优化）
O(n!)	阶乘阶	全排列算法

计算时间复杂度

1. 找出基本操作：通常是循环体内的最内层语句，或递归调用次数。

2. 计算基本操作执行次数与 n 的关系。

3. 用大O表示法简化。

一层循环：

for (int i = 0; i < n; i++) {
    // 基本操作
}

这一层的基本操作执行 n 次 → O(n)

第二层循环：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 基本操作
    }
}

内层循环每次执行 n 次，外层 n 次 → 总计 n^2 → O(n^2)

二分法寻找目标：

while (low <= high) {
    mid = (low + high) / 2;
    if (target == arr[mid]) return mid;
    else if (target < arr[mid]) high = mid - 1;
    else low = mid + 1;
}

每次将搜索范围减半，最多执行 log⁡(n,2) 次 → O(log⁡(n))

递归关系：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

递归调用树近似二叉树，节点数 2^n 级别 → O(2^n)

若使用动态规划（循环）则降为 O(n)

• 只看最内层循环。

• 加法法则：总复杂度取最大项（顺序执行）。

• 乘法法则：嵌套循环复杂度相乘。

随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。

1、用常数1取代运行时间中的所有基本操作。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

空间复杂度：

对一个算法在运行过程中临时占用存储空间大小的量度

空间复杂度表示算法运行过程中临时占用的内存空间（不包括输入数据本身）随数据规模增长的趋势。也用大O表示。

• O(1)：常数空间，只用了几个变量。

• O(n)：线性空间，如数组、递归栈深度与 nn 成正比。

• O(n^2)：二维数组。

计算空间复杂度

1. 计算算法中额外分配的变量、数组、递归栈等所占空间。

2. 忽略输入数据本身的空间（因为输入是必须的），只考虑辅助空间。

3. 用大O表示。

集合计算：

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
}

只用了 sum 和 i 两个变量 → O(1)

分配空间：

int *arr = (int*)malloc(n * sizeof(int));
// 使用 arr...
free(arr);

动态分配了 n 个整数的空间 → O(n)

递归关系：

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

递归深度为 n，每次调用需要保存返回地址等 → 空间复杂度 O(n)

分配两层空间：

int **matrix = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
    matrix[i] = (int*)malloc(n * sizeof(int));
}

总空间 n×n 个整数 → O(n^2)

复杂度分析基于渐进分析（asymptotic analysis）：

• 只关心当 n 趋近无穷大时的行为。

• 忽略常数因子和低阶项，因为它们在 n 很大时影响微不足道。

• 最坏情况分析：通常我们关注算法在最坏输入下的表现（如快速排序最坏 O(n^2)）。

• 平均情况分析：有时也需要，但一般先掌握最坏情况。

数据结构与算法

数据的逻辑结构是从逻辑关系上描述数据，主要包含：

• 数据元素（节点）

• 元素之间的关系（前驱、后继、父子等）

通常分为四大类：集合结构、线性结构、树形结构、图状结构（或称网状结构）

结构类型	关系特征	常见例子
集合	元素之间无任何关系	哈希表、集合容器
线性结构	一对一关系	数组、链表、栈、队列
树形结构	一对多关系	二叉树、堆、B树
图状结构	多对多关系	社交网络图、交通路线图

集合结构

集合结构中的数据元素之间没有明确的关系，它们只是“同属于一个集合”。集合中的元素通常具有互异性（不重复）和无序性（逻辑上无序）。

• 元素之间无前驱、后继、父子等关系。

• 操作主要围绕元素是否存在、插入、删除、集合运算（并、交、差）等。

常见实现

• 哈希表（如 C++ 的 unordered_set）

• 平衡二叉搜索树（如 C++ 的 set，逻辑上仍为集合，但内部有序）

集合 S = {3, 5, 7, 9}
无法说谁在谁前面，谁是谁的父节点。

线性结构

线性结构中的元素之间存在一对一的关系，即除了第一个和最后一个元素外，每个元素有且仅有一个直接前驱和一个直接后继。

• 数据元素按顺序排列，具有线性次序。

• 通常支持遍历、按位置访问（不一定随机）、插入、删除等操作。

名称	特点	存储方式	典型操作
线性表（顺序表）	逻辑上连续，物理上通常连续	数组	随机访问、插入删除慢
链表	逻辑连续，物理不连续	节点+指针	插入删除快，随机访问慢
栈	后进先出（LIFO）	顺序或链式	push/pop，top
队列	先进先出（FIFO）	顺序或链式	enqueue/dequeue
串	字符组成的线性表	数组或链	模式匹配、拼接

L = [a1, a2, a3, ..., an]
a1 无前驱，a2 的前驱是 a1，后继是 a3，...，an 无后继。

树形结构

树形结构中的元素之间存在一对多的关系，即一个节点可以有多个子节点，但每个子节点只有一个父节点（根节点除外）。

• 有且仅有一个根节点。

• 除根节点外，每个节点有且仅有一个前驱（父节点）。

• 一个节点可以有零个或多个后继（子节点）。

• 没有环路。

常见树形结构

• 二叉树：每个节点最多有两个子节点。

• 二叉搜索树：左子树所有节点 < 根节点 < 右子树。

• 堆：完全二叉树，用于优先队列。

• B树 / B+树：多路搜索树，用于数据库索引。

• 平衡树（AVL、红黑树）：自平衡的二叉搜索树。

        A
       / \
      B   C
     / \   \
    D   E   F

A 是根，B、C 是 A 的孩子，D、E 是 B 的孩子，F 是 C 的孩子。

图状结构（网状结构）

图结构中的元素之间存在多对多的关系，即任意两个节点之间都可能存在关系，且关系可以有方向（有向图）或无方向（无向图），可以有环。

• 节点之间关系任意，没有严格的前驱后继限制。

• 可以存在回路。

• 是树结构的推广（树是无环连通图）。

常见图结构

• 有向图：边有方向，如网页链接关系。

• 无向图：边无方向，如社交网络好友关系。

• 加权图：边带有权值，如地图距离。

• 邻接矩阵 / 邻接表：常用存储方式。

    A
   / \
  B---C

A、B、C 之间彼此连接，A 和 B、A 和 C、B 和 C 都有边。

结构类型	关系	常见操作	典型应用
集合	无关系	插入、查找、删除、集合运算	去重、成员检测
线性	一对一	遍历、访问、插入、删除	数组、栈、队列、链表
树形	一对多	查找、插入、删除、遍历	文件系统、数据库索引、编译器语法树
图状	多对多	搜索、最短路径、最小生成树	网络路由、社交网络、地图导航

数据的物理存储结构

物理存储结构是指数据在计算机内存（或外存）中的实际存放方式。它直接影响：

• 存取速度（随机存取 vs 顺序存取）

• 空间利用率

• 插入、删除等操作的效率

存储结构	核心特点	典型代表
顺序存储	逻辑相邻的元素在物理上也相邻	数组
链式存储	逻辑相邻的元素在物理上不一定相邻，通过指针链接	单链表、双链表
索引存储	建立索引表，通过索引快速定位数据	索引文件、数据库索引
散列存储	通过哈希函数直接计算存储位置	哈希表

顺序存储结构（Sequential Storage）

顺序存储结构是指：将数据元素存放在一组地址连续的存储单元中，逻辑上相邻的元素在物理内存中也相邻。

• 每个元素占用的存储单元大小相同（或可计算）。

• 通过起始地址 + 偏移量即可直接计算出任意元素的地址，从而实现随机存取。

Loc(a[i]) = Loc(a[0]) + i × sizeof(元素类型)

其中 Loc(a[0]) 是首元素的地址，sizeof(元素类型) 是每个元素占用的字节数。

冒泡

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;  // 优化标志，若本轮无交换则提前结束
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

快速

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选最后一个元素为基准
    int i = low - 1;        // 指向小于基准的最后一个位置
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准放到正确位置
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;  // 返回基准最终索引
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}