一基本概念和术语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) { // 执行N1次最后一次判断不进入循环 ret i; // 执行N次 i; // 执行N次 } return ret; // 执行1次 }总执行次数f(N) 11(N1)NN1 3N4次。三、时间复杂度渐进表示法大O表示法1. 为什么需要渐进表示我们真正关心的不是小数据量下的绝对执行次数而是当输入规模N无限增大时算法执行次数的增长速度增长趋势。例如- 算法A(N)100*N- 算法B(N)当N50时A执行5000次B执行2500次B更快但当N1000时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)3N4简化后时间复杂度为T(N)O(N)。六常见样例分析样例1O(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)典型场景数组遍历、链表遍历、顺序查找。样例2O(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]); } } } }计算过程总比较交换次数 123...(n-1) \frac{n(n-1)}{2}保留最高阶项忽略系数和低阶项。结论T(N)O()典型场景冒泡排序、选择排序、插入排序。样例3O(N³) 立方级核心特征三层嵌套循环每层循环次数都与 N 成正比。样例3N阶方阵乘法 #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最短路径算法。样例4O(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)典型场景二分查找、二叉树高度计算、快速幂算法。样例5O(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)典型场景数组随机访问、哈希表查找、简单算术运算。样例6O(MN) 多变量线性级核心特征多个独立的循环分别对应不同的输入规模。样例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(MN) 或 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共调用N1次- 每次递归内部的操作乘法和条件判断都是O(1)- 总复杂度(N1)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)的原地算法在内存受限场景下是刚需
【数据结构入门①】从数据结构概念到复杂度分析
发布时间：2026/6/8 17:00:11
一基本概念和术语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) { // 执行N1次最后一次判断不进入循环 ret i; // 执行N次 i; // 执行N次 } return ret; // 执行1次 }总执行次数f(N) 11(N1)NN1 3N4次。三、时间复杂度渐进表示法大O表示法1. 为什么需要渐进表示我们真正关心的不是小数据量下的绝对执行次数而是当输入规模N无限增大时算法执行次数的增长速度增长趋势。例如- 算法A(N)100*N- 算法B(N)当N50时A执行5000次B执行2500次B更快但当N1000时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)3N4简化后时间复杂度为T(N)O(N)。六常见样例分析样例1O(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)典型场景数组遍历、链表遍历、顺序查找。样例2O(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]); } } } }计算过程总比较交换次数 123...(n-1) \frac{n(n-1)}{2}保留最高阶项忽略系数和低阶项。结论T(N)O()典型场景冒泡排序、选择排序、插入排序。样例3O(N³) 立方级核心特征三层嵌套循环每层循环次数都与 N 成正比。样例3N阶方阵乘法 #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最短路径算法。样例4O(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)典型场景二分查找、二叉树高度计算、快速幂算法。样例5O(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)典型场景数组随机访问、哈希表查找、简单算术运算。样例6O(MN) 多变量线性级核心特征多个独立的循环分别对应不同的输入规模。样例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(MN) 或 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共调用N1次- 每次递归内部的操作乘法和条件判断都是O(1)- 总复杂度(N1)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)的原地算法在内存受限场景下是刚需
