一，基本概念和术语
1，数据：数据是对客观事物的符号表示，是信息的载体，可以是数字，字符，字符串，图像，声音等。如：182，“李四”，94，“男”。
2，数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由多个数据项构成，数据项是数据不可分割的最小单位。
如一个结构体{"张三","男","2314050654"}是一个学生的完整信息，也是一个数据元素，其中的学号，姓名等就是一个数据项。
3，数据对象：具有相同性质的数据元素的集合。如老师手里的点名表，有全班同学的姓名，性别，学号。那点名表就是一个数据对象。包含了学生A到学生Z的数据元素。
一句话总结
多个数据项拼出1个数据元素（单个学生），无数同类型数据元素汇总成1个数据对象（全班学生）。
二，数据结构三要素
1，什么是数据结构：数据之间不是独立存在的，它们之间存在某种关系，数据元素之间的关系称为结构。
2，数据结构包含三个方面的内容(三要素)：逻辑结构，物理结构(存储结构)，数据运算和实现。
3，逻辑结构：描述数据元素之间的逻辑关系。逻辑结构可分为：线性结构、树形结构、图形结构(网状结构)、集合。也可以直接分为线性结构和非线性结构。
①线性结构：线性结构中的数据元素之间存在一对一的关系，除了第一个元素，所有元素都有唯一前驱，除了最后一个元素，所有元素都有唯一后继。非线性结构可能有多个直接前驱和直接后继。
如排队时人们的关系。
②树形结构：树形结构中的数据元素之间存在一对多的关系。
如电脑文件的保存关系。
③图形结构：图形结构中的数据元素之间存在多对多的关系。
如日常生活中的社交关系。
④集合：集合中的数据元素属于一个集合，除此之外别无其他关系。
4，物理结构(存储结构)：数据元素及其关系在计算机的存储结构中表示，物理结构主要有四种：顺序存储、链式存储、索引存储、散列存储。
①顺序存储：把逻辑上相邻的数据元素存放在一段连续物理存储单元中，数据元素之间的逻辑关系可以由物理存储关系体现。如存放在数组中。
②链式存储：逻辑上相邻的数据元素存储在任意的一组物理存储单元中，数据元素之间的逻辑关系用指针来表示。
③索引存储：存储元素信息的同时，还建立了索引表，索引表中的每项称为索引项，索引项的一般形式为(关键字，地址)。就像是一个目录，用来查找对应数据。
④散列存储：根据数据元素中的关键字计算出该数据元素的存储地址。
5，数据运算和实现：对数据元素可以施加的操作，以及这些操作在相应的存储结构上的实现。
三，数据类型和抽象数据类型
数据类型是一个值的集合和定义在这个值集上的一组操作的总称，数据类型一般可分为：原子类型和结构类型。
a. 原子类型：原子类型的值是不可以再分解的。如C语言的int、double、char等基本数据类型
b. 结构类型：结构类型的值是由若干成分按某种结构组成，是可以分解的。如C语言中定义的一个结构体类型。
抽象数据类型：Abstract Data Type, ADT：是一种数学模型加上在该模型上定义的一组操作的集合，它定义了数据对象、数据关系以及对数据的操作，但隐藏了具体实现细节。
四，算法的基本概念
1，算法是解决特定问题的求解步骤的一种描述。
2，算法 + 数据结构 = 程序。
3，算法的特性：
①有穷性：算法必须在有限步骤内结束，禁止无限循环，永不终止。
②确定性：算法每一条指令定义精准、无歧义，相同输入经过运算，必定得到完全一致的输出结果。
③可行性：算法中所有运算步骤，都能依托已实现的基础运算有限次落地执行。
④输入：输入数量≥0，输入数据来源于指定的数据对象集合。
⑤输出：输出数量≥1，输出结果由输入数据经过算法处理生成，和输入具备对应逻辑关系。
4，算法的设计要求
①正确性
算法能够精准完成目标问题求解，针对合法输入产出正确答案。
②可读性
代码逻辑思路通俗易懂、注释规范，便于后续阅读、调试与二次维护。
③健壮性
面对非法、异常输入时，算法可合理处理异常，不会出现崩溃、乱输出等莫名错误。
④高效率与低存储（时空性能）
- 时间效率：尽可能缩短代码运行耗时；
- 空间效率：程序运行期间占用的内存资源越少越好；
二者合称算法的时间复杂度、空间复杂度，是衡量算法优劣的核心指标。
五，算法的时间复杂度
一、为什么要分析算法效率
同一个问题可以有多种不同的算法实现，评价一个算法的优劣有明确的优先级：
正确性 > 可读性 > 健壮性 > 算法效率
在满足前三个基本要求后，我们主要通过算法效率来选择最优方案。算法效率分为两类：
- 时间效率：算法运行时所耗费的时间
- 空间效率：算法运行过程中额外耗费的存储空间
现在重点讲解最常用的时间效率分析方法——时间复杂度。
二、时间效率的两种分析方法
1. 事后统计法
先完整实现算法，然后运行并统计实际耗时。
缺点：严重依赖运行环境（编程语言、CPU、编译器、操作系统），不同机器上的结果差异极大，好的设备就快，不好的设备就慢，容易掩盖算法本身的优劣；且必须先写代码才能测试，成本高。
2. 事前估算法（核心方法）
在代码编写前，通过数学方法估算算法的执行效率，完全脱离硬件和软件环境，是行业通用的标准方法。
事前估算的核心公式
算法的总运行时间 = 所有代码语句的执行时间之和
运行时间 =
-：第 i 条语句单次执行消耗的时间(与硬件，编译器相关)。
-:第 j 条代码语句的执行次数(仅与算法逻辑相关)。
公式简化
由于与算法本身无关，为了统一标准，我们做一个合理假设：所有代码语句单次执行的时间相同，即
=1。
此时，算法的运行时间就简化为所有代码语句的执行次数之和，记为函数f(N)（N为输入数据的规模）。
示例：累加算法的事前估算
int Summation(int N) { int ret = 0; // 执行1次 int i = 1; // 执行1次 while (i <= N) { // 执行N+1次（最后一次判断不进入循环） ret += i; // 执行N次 i++; // 执行N次 } return ret; // 执行1次 }总执行次数：f(N) = 1+1+(N+1)+N+N+1 = 3N+4次。
三、时间复杂度渐进表示法（大O表示法）
1. 为什么需要渐进表示
我们真正关心的不是小数据量下的绝对执行次数，而是当输入规模N无限增大时，算法执行次数的增长速度（增长趋势）。
例如：
- 算法A：(N)=100*N
- 算法B：(N)=
当N=50时，A执行5000次，B执行2500次，B更快；但当N=1000时，A执行100000次，B执行1000000次，A快得多。随着N继续增大，A的优势会越来越明显。
因此，算法分析的核心是比较执行次数随规模变化的增长速度，而不是具体的数值。
2. 大O表示法的数学定义
若存在常数C和，使得当
时，有
，则称T(N)的渐进时间复杂度为O(f(N))，简称时间复杂度。
(C为非零有限常数)
大O表示法描述的是算法运行时间的上界，即最坏情况下的增长趋势。
3. 大O表示法的计算规则
对执行次数函数f(N)做如下简化，即可得到时间复杂度：
①只保留最高阶项：当N无限大时，最高阶项对增长速度起决定性作用
②去除最高阶项的系数：系数不影响增长量级
③去除所有常数项：常数项与输入规模N无关
④若没有与N相关的项（只有常数）：时间复杂度记为O(1)
4，快速计算技巧（实战必备）
实际开发中不需要逐行统计执行次数，记住以下技巧即可快速判断：
1. 只关注循环语句：普通语句的执行次数都是常数，可以直接忽略
2. 只看循环内部的基本操作：循环的条件判断、自增等语句的影响最终都会被系数抵消
3. 嵌套循环看层数：一层循环通常是O(N)，两层嵌套是O()，三层是O(
)注意：不是所有循环都是O(N)，例如二分查找的循环是O(logN)，需要结合具体逻辑计算
5. 对数的统一表示
根据对数换底公式：
其中是一个常数，因此所有底数的对数在渐进表示中都是同一量级。
行业通用写法：统一用O(logN)表示，部分书籍也会写成O(lgN)。
四、常见时间复杂度量级排序
从最优到最差的顺序：
O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(N^3) < O(2^N) < O(N!)
- O(1)：常数级，最优，如数组随机访问
- O(logN)：对数级，非常高效，如二分查找
- O(N)：线性级，如遍历数组
- O(N*logN)：线性对数级，如快速排序、归并排序
- O()：平方级，如冒泡排序、选择排序
- O()、O(N!)：指数级和阶乘级，效率极低，仅适用于极小数据量
五、经典样例分析
O(N) 线性级
对应上面的累加算法，总执行次数f(N)=3N+4，简化后时间复杂度为T(N)=O(N)。
六，常见样例分析
样例1：O(N) 线性级
核心特征：单层循环，循环次数与输入规模 N 成正比。
// 样例1：累加求和算法 int Summation(int N) { int ret = 0; int i = 1; while (i <= N) { ret += i; i++; } return ret; }
计算过程：循环体 ret += i 和 i++ 各执行N次，忽略常数项和系数。
结论：T(N)=O(N)
典型场景：数组遍历、链表遍历、顺序查找。
样例2：O(N²) 平方级
核心特征：两层嵌套循环，每层循环次数都与 N 成正比。
样例2：冒泡排序算法 #include <assert.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void BubbleSort(int* a, int n) { assert(a); // 外层循环控制排序轮数 for (size_t end = n; end > 0; --end) { // 内层循环进行相邻元素比较交换 for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); } } } }计算过程：
总比较交换次数 = 1+2+3+...+(n-1) = \frac{n(n-1)}{2}
保留最高阶项，忽略系数和低阶项。
结论：T(N)=O()
典型场景：冒泡排序、选择排序、插入排序。
样例3：O(N³) 立方级
核心特征：三层嵌套循环，每层循环次数都与 N 成正比。
样例3：N阶方阵乘法 #define N 3 void MatrixMultiply(int A[][N], int B[][N], int C[][N]) { // 核心计算部分：三层嵌套循环（决定最高阶） for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i][j] = 0; for (int k = 0; k < N; k++) { C[i][j] += A[i][k] * B[k][j]; } } } // 打印结果（O(N²)，低阶项不影响最终复杂度） for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", C[i][j]); } printf("\n"); } }计算过程：核心乘法部分执行次，打印部分执行
次，只保留最高阶项。
结论：T(N)=O()
典型场景：矩阵乘法、Floyd最短路径算法。
样例4：O(logN) 对数级（极高效）
核心特征：循环变量每次按倍数增长/衰减（×2、÷2等）。
样例4：倍增循环计数 #include <stdio.h> void Count(int n) { // i从1开始，每次乘以2，直到大于n for (int i = 1; i < n; i *= 2) { printf("%d\n", i); } }计算过程：
设循环执行了x次，则终止条件为
两边取对数得：
所有底数的对数在大O表示中是同一量级，统一记为O(logN)。
结论：T(N)=O(logN)
典型场景：二分查找、二叉树高度计算、快速幂算法。
样例5：O(1) 常数级（最优）
核心特征：执行次数是固定常数，与输入规模 n 完全无关。
样例5：固定次数打印 void Print100(int* a, int n) { // 循环最多执行100次，无论n多大都不变 for (int i = 0; i < n && i < 100; i++) { printf("%d ", a[i]); } printf("\n"); }计算过程：循环执行次数≤100，是一个固定常数。
结论：T(N)=O(1)
典型场景：数组随机访问、哈希表查找、简单算术运算。
样例6：O(M+N) 多变量线性级
核心特征：多个独立的循环，分别对应不同的输入规模。
样例6：两个独立循环打印 void PrintMN(int m, int n) { // 第一个循环执行m次 for (int i = 0; i < m; ++i) { printf("hello\n"); } // 第二个循环执行n次 for (int i = 0; i < n; ++i) { printf("hello\n"); } }计算过程：总执行次数 = m + n，取最高阶项。
结论：T(N)=O(M+N) 或 O(max(M,N))
实战技巧：多个独立循环的复杂度相加，只保留最大的那个量级。
样例7：最好、最坏、平均时间复杂度
有些算法的执行次数会随输入数据的分布而变化，因此需要分三种情况讨论：
- 最坏时间复杂度：最坏情况下的执行次数（行业默认使用，保守估计）
- 最好时间复杂度：最好情况下的执行次数（算法下限）
- 平均时间复杂度：所有输入情况的期望执行次数
int Find(int* a, int n, int x) { for (int i = 0; i < n; i++) { if (a[i] == x) { return i; // 找到就立即返回 } } return -1; // 没找到 }详细分析：
1. 最好情况：要找的元素在数组第一个位置，执行1次 → T(N)=O(1)
2. 最坏情况：要找的元素在数组最后一个位置或不存在，执行n次 → T(N)=O(N)
3. 平均情况：假设每个位置出现的概率相等，平均执行次数为：
→ T(N)=O(N)
重要结论：我们平时说的算法时间复杂度，默认指的是最坏时间复杂度。
样例8：递归算法的时间复杂度
核心公式：递归算法的时间复杂度 = 递归调用的次数 × 每次递归内部的操作复杂度。
样例8：递归求阶乘 long long Fac(size_t N) { if (0 == N) { return 1; // 递归终止条件，O(1) } return Fac(N-1) * N; // 递归调用，O(1) }计算过程：
- 递归调用次数：从N到0，共调用N+1次
- 每次递归内部的操作：乘法和条件判断，都是O(1)
- 总复杂度：(N+1)O(1) = O(N)
结论：T(N)=O(N)
七、核心总结
1. 时间复杂度描述的是算法运行时间随输入规模增长的趋势，不是绝对运行时间
2. 大O表示法关注的是最坏情况下的增长量级，忽略常数、系数和低阶项
3. 计算时间复杂度时，只需要看循环的嵌套层数和逻辑，不需要逐行统计
4. 时间复杂度是衡量算法优劣的核心指标，也是面试中算法题的必考内容
六，空间复杂度分析
一、核心定义
空间复杂度描述的是算法为了实现功能，额外开辟的存储空间随输入规模N增长的变化趋势。
⚠️ 最关键的区分：算法输入数据本身占用的空间不计入空间复杂度，我们只统计算法为了完成计算，主动申请的临时变量、数组、栈、队列等额外空间。
二、计算方法（与时间复杂度完全一致）
和时间复杂度的事前估算法逻辑完全相同，步骤如下：
1. 假设每个基础变量占用的空间大小为1（忽略不同数据类型的字节差异）
2. 统计算法运行过程中，额外申请的所有变量/空间的总数量，得到函数f(N)
3. 保留最高阶项，忽略所有常数项和系数，最终用大O表示法记为 S(N)=O(f(N))
三、常见空间复杂度量级（从优到劣）
和时间复杂度的量级排序完全一致，日常开发中最常用的是前四个：
O(1)好于O(logN)好于O(N)好于O()
- O()、O(N!) 等指数/阶乘级空间复杂度在实际工程中几乎不会使用。
四、核心概念：原地算法
如果算法在执行过程中，只需要常数级别的额外空间（即空间复杂度为O(1)），就称为原地算法。
原地算法是空间效率最优的算法，不需要额外开辟大量内存，在嵌入式、大数据等内存受限的场景中尤为重要。
五、时间复杂度 vs 空间复杂度 核心对比
维度 时间复杂度 空间复杂度
核心关注点 算法执行次数的增长趋势 算法额外空间的增长趋势
计算依据 循环、递归的执行次数 额外申请的变量、数组数量
最优情况 （常数次执行） （原地算法）
计算规则 保留最高阶，忽略常数和系数 与时间复杂度完全相同
六、核心总结
1. 时间看“跑多久”，空间看“占多少内存”，二者计算规则完全一致
2. 空间复杂度只算算法自己额外申请的空间，输入数据的空间不算
3. 算法设计中常做时空权衡：用少量额外空间换取更快的运行速度，或用更长的运行时间节省内存
4. 优先追求O(1)的原地算法，在内存受限场景下是刚需
