目录一、数据结构基础四大术语二、数据结构三要素2.1 逻辑结构元素之间抽象逻辑关系2.2 物理结构存储结构内存中真实怎么存放2.3 数据运算和实现对数据可以执行的操作补充抽象数据类型 ADT三、算法基础概念3.1 算法五大特性3.2 评判好算法的 4 个标准四、算法的时间复杂度4.1 如何分析算法的时间效率4.2 时间复杂度渐进表示法4.3 时间复杂度经典样例分析4.3.1 样例1O(N) 级4.3.2 样例2O(N^2) 级4.3.3 样例3O(N^3) 级4.3.4 样例4O(logN) 级4.3.5 样例5O(1) 常数阶4.3.6 样例6O(MN)4.3.7 样例7顺序查找最好/最坏/平均4.3.8 样例8递归阶乘O(N)4.4 经典题目五、空间复杂度渐进表示法5.1 什么是空间复杂度5.2 经典样例分析一、数据结构基础四大术语层级关系数据对象 (集合) ⊇ 数据元素 (个体) ⊇ 数据项 (最小属性)表格名词通俗解释举例数据能被计算机处理的所有符号总称数字、文字、图片、音频数据项不可分割最小单位代表一个属性学号、姓名、分数数据元素数据的基本处理单位一个完整个体由多个数据项组成一个学生全部信息 {学号姓名成绩}数据对象相同性质的数据元素的集合数据的子集全班学生花名册用 C 语言结构体直观理解typedef struct { int id; // 数据项学号 char name[20]; // 数据项姓名 char gender[3]; // 数据项性别 double score; // 数据项绩点 }Student; int main() { // arr数组【数据对象】全班学生集合 // arr[0],arr[1]【数据元素】单个学生信息 // id、name、gender【数据项】学生的单个属性 Student arr[] { {10001, 张三, 男, 3.0}, {10002, 李四, 女, 3.5}, {10003, 王五, 男, 2.0} }; }二、数据结构三要素定义数据结构 带结构的数据元素的集合数据元素不是孤立存在互相之间存在关系。 三要素逻辑结构、物理存储结构、数据运算与实现。2.1 逻辑结构元素之间抽象逻辑关系只关心逻辑上的关系不管内存怎么存放分为线性、非线性。线性结构一对一除头元素没有前驱尾元素没有后继其余每个元素唯一前驱、唯一后继。 例子医院排队叫号、数组、链表、栈、队列。树形结构一对多例子电脑文件夹目录、企业组织架构。图形 / 网状结构多对多例子社交软件好友关系人和人可以互相认识。集合结构元素仅仅属于同一个集合元素之间没有其他约束关系。记忆树形、图形、集合统称为非线性结构。2.2 物理结构存储结构内存中真实怎么存放逻辑关系在计算机内存的真实映射一共 4 种存储方式1. 顺序存储逻辑相邻的元素放在物理连续的内存空间逻辑关系靠内存位置体现。代表数组。优点支持随机访问缺点中间插入删除需要挪动大量数据。2. 链式存储逻辑相邻物理地址可以散乱不连续依靠指针保存下一个元素的地址。代表链表。不需要连续大块内存插入删除方便不支持随机访问。3. 索引存储除了存储原始数据额外维护一张索引表索引项格式(关键字内存地址)通过索引快速定位元素。4. 散列哈希存储拿元素关键字通过哈希函数直接计算得到存储地址直接存放元素。考点提醒运算的实现依赖存储结构。 举个例子同样是 “插入” 操作顺序表数组和链表的代码实现完全不一样。2.3 数据运算和实现对数据可以执行的操作增、删、改、查以及这些操作在对应存储结构上的代码实现。补充抽象数据类型 ADTADT 数据对象 (D) 数据关系 (S) 基本操作 (P) 只规定对外提供什么功能接口隐藏底层实现细节。不管底层是数组实现还是链表实现对外接口不变。伪代码示例栈的 ADT 描述ADT Stack { 数据对象:D {aᵢ | aᵢ ∈ ElemType, i 1,2,...,n, n ≥ 0} 数据关系:S {aᵢ₋₁, aᵢ | aᵢ₋₁, aᵢ ∈ D, i 2,...,n} 约定aₙ为栈顶,a₁为栈底 基本操作: InitStack(S); //初始化栈 DestroyStack(S); //销毁栈 StackEmpty(S); //判栈空 Push(S, e); //入栈 Pop(S, e); //出栈 GetTop(S, e); //获取栈顶元素 }三、算法基础概念著名公式程序 数据结构 算法—— 图灵奖得主 Niklaus Wirth (Pascal 之父)数据结构负责数据如何组织存放算法处理数据的步骤指令序列 二者相辅相成同一个问题选用不同的数据结构算法的效率天差地别。3.1 算法五大特性有穷性有限步骤之后必须结束不能无限死循环。程序可以死循环算法不行确定性每一步定义明确无二义相同输入一定得到相同输出。可行性所有操作都可以由基础运算有限次完成。输入0 个或者多个输入。输出1 个或者多个输出。3.2 评判好算法的 4 个标准正确性可以正确解决问题可读性代码逻辑易懂方便阅读维护健壮性输入非法数据不会直接崩溃可以合理处理异常高效率、低存储运行时间短占用额外内存少。四、算法的时间复杂度4.1 如何分析算法的时间效率写代码时我们经常会被问到这段代码的时间复杂度是多少 同样一个需求可以写出多种实现代码。怎么判断哪个算法性能更好 评判算法好坏不只是看能不能算出正确结果还要看效率。效率分为时间效率和空间效率。时间效率算法运行需要花费多久空间效率算法运行时额外占用多少内存评估时间效率有两种方案事后统计法写完代码直接运行看耗时。 缺点严重依赖硬件、编程语言、编译器环境。同样代码电脑配置不同运行速度差别很大无法单纯评判算法本身好坏而且必须先写出代码才能测试。事前估算不用实际运行代码预估代码语句执行次数脱离硬件环境直接评估算法本身。这就是我们要学习的重点。事前估算统计语句执行次数事前估算公式算法运行时间单条语句执行一次消耗的时间这条语句执行多少次。和 CPU、语言环境相关做估算时我们可以直接假设只统计语句总执行次数。举一段 C 语言累加求和代码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\)f(N)的含义输入数据规模为 N 时代码一共要执行多少次操作。问题来了我们直接用 \(3N4\) 对比算法可行吗不行。4.2 时间复杂度渐进表示法举个例子算法 A100×N算法 BN*NN50A 执行 5000 次B 执行 2500 次 → B 更快N1000A 执行 10 万次B 执行 100 万次 → A 更快✅核心思想分析算法我们关心 N 很大时候的增长趋势不在乎 N 很小的时候谁更快。当输入规模无限变大式子里面最高次项才会主导增长速度常数、低次项的影响会被无限弱化。渐进时间复杂度简称时间复杂度记作描述输入规模 N 趋向无穷大时算法操作次数的增长趋势。✅ 大 O 化简 4 条规则记牢只保留最高阶项去掉最高阶项前面的系数去掉所有常数项如果没有和 N 相关的项全是常数复杂度记为O(1)。一句话口诀抓大头扔系数丢常数示例f(N)3N4→ 保留最高项 N去掉系数 →O(N)f(N)10N^35N^2N100→O(N^3)f(N)100N^210000→ O(N^2)实战快速估算技巧不需要逐行统计所有代码日常分析有简单套路普通单行语句都是常数直接忽略重点只看循环。循环内部只需要看核心基础操作。循环条件、变量自增这些最后都会变成系数化简时直接丢掉。for(int i 0; i n; i){ x; }只看x执行 n 次 →O(N)嵌套循环看循环层数⚠️这是一般情况不是绝对单层循环大多 O(N)两层嵌套循环大多 O(N^2)三层嵌套循环大多 O(N^3)⚠️ 重要提醒不是所有嵌套循环都是平方阶。比如二分查找那种每次循环范围减半复杂度是对数阶一定要看循环变量的变化逻辑不能只看嵌套层数。常见时间复杂度量级由快到慢O(1) O(logN) O(N) O(NlogN) O(N^2) O(N^3) O(2^N) O(N!)表格复杂度名称说明O(1)常数阶无论 N 多大操作次数固定。例如公式直接计算结果O(logN)对数阶每次操作把问题规模减半典型二分查找O(N)线性阶单层循环数据量翻倍执行次数翻倍O(NlogN)线性对数阶一层循环嵌套对数操作快排、归并排序O(N^2)平方阶两层嵌套循环冒泡排序O(N^3)立方阶三层嵌套循环O(2^N)指数阶暴力递归枚举N 稍微变大次数爆炸O(N!)阶乘阶全排列暴力解法性能极差尽量避免对数小知识点 根据对数换底公式对数底数只是一个常数系数。 logaN 和 logbN 属于同一个量级所以统一写成 O(logN)不用区分底数是 2 还是 10。复杂度增长趋势解读✅优秀O(1)、O(logN)增长极其缓慢✅尚可O(N)、O(NlogN)工程代码最常用⚠️较差O(N^2)、O(N^3)大数据量下性能很差❌灾难O(2^N)、O(N!)数据规模稍微大一点程序就跑不动总结一句话时间复杂度大 O不是代码真实运行时间它是衡量当输入数据越来越多的时候算法执行次数增长有多快。 分析的时候抓住最高阶项丢掉常数和系数就可以快速得到时间复杂度。4.3 时间复杂度经典样例分析4.3.1 样例1O(N) 级int Summation(int N) { int ret 0; int i 1; while (i N) { ret i; i; } return ret; }循环执行N次每次循环内操作是常数次O(1)T(N)O(N)4.3.2 样例2O(N^2) 级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]); } } } }总比较次数12...nn(n1)/2最高阶n^2T(N)O(N^2)4.3.3 样例3O(N^3) 级#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²)低阶忽略 }三层嵌套循环每层循环N次T(N)O(N^3)4.3.4 样例4O(logN) 级void Count(int n) { for (int i 1; i n; i * 2) { printf(%d\n, i); } }每次i *2设循环x次只要循环变量成倍增长 / 成倍缩小一般都是对数阶4.3.5 样例5O(1) 常数阶void Print100(int* a, int n) { for (int i 0; i n i 100; i) { printf(%d , a[i]); } }最多循环固定 100 次和输入规模n无关常数次O(1)✅判断要点循环次数是固定常数不随 n 变大而增加4.3.6 样例6O(MN)void PrintMN(int m, int n){ for (int i 0; i m; i){ printf(hello\n); } for (int i 0; i n; i){ printf(hello\n); } }两个独立循环总次数MNTO(MN)也可写成O(max(M,N)4.3.7 样例7顺序查找最好/最坏/平均int Find(int* a, int n, int x) { for (int i 1; i n; i) { if (a[i] x) return i; } return -1; }最好第一个元素就找到 → O(1)最坏最后一个才找到 / 不存在 → O(N)平均最高阶O(N)算法时间复杂度默认取最坏情况保守估算4.3.8 样例8递归阶乘O(N)long long Fac(size_t N){ if (0 N) return 1; return Fac(N-1)*N; }递归调用N1次每次递归内部操作O(1)递归时间复杂度 递归调用次数 × 每次递归内部工作量T(N)O(N)4.4 经典题目题1x 2; while ( x n/2 ) x 2*x;设循环t次循环结束条件复杂度题2int fact (int n) { if (n 1) return 1; return n * fact(n-1); }递归n次每次内部O(1)O(n)题3count 0; for(k1; kn; k*2) for(j1; jn; j) count;假设第⼀层循环执行x次则循环结束时 因为循环次数x是整数则xlog2n 1 第二层循环每次都执行N次则整体时间复杂度为O(n∗log2n)题4int func(int n) { int i0, sum0; while(sum n) sum i; return i ; }每次循环sum 123...x循环结束时可以推出题5x0; while (n (x1)*(x1)) xx1;假设循环执行t次每次循环x递增1;循环结束时则n (x 1)^2x从0开始则xt则n (t 1)^2 则整体时间复杂度为O(n^(1/2))时间复杂度速记表代码特征复杂度单层循环iO(N)两层嵌套循环O(N2)三层嵌套循环O(N3)i *2 / i /2O(logN)循环次数固定常数O(1)循环累加 12…t ≥nO(n​^(1/2))递归每次 n-1O(N)解题步骤看循环变量怎么变i线性i*2对数x*x平方根写出循环终止不等式解循环次数t取最高阶去掉常数写大 O递归统计递归调用次数 × 单次内部复杂度五、空间复杂度渐进表示法5.1 什么是空间复杂度和时间复杂度思想类似事前估算算法额外占用内存空间的增长量级使用大 O 渐进表示法。⚠️ 核心重点 空间复杂度统计的是算法为实现功能额外开辟的空间。 输入数据本身占用的内存不计入空间复杂度空间复杂度估算思路例如下面这段代码double Func(int N) { double ret 0; // C11个变量 int i 1; // C21个变量 char tmp[N]; // C3N个变量 while (i N) { ret i; i; } return ret; }函数占用空间f(N)C1*1C2*1C3*NC1,C2,C3代表单个变量/数组元素占用字节数属于与N无关的常熟。合并常数项f(N)(C1C2)C3*N渐进分析时丢弃常数项与常熟系数只保留最高阶项得到空间复杂度S(N)O(N)常见空间复杂度量级从小到大1.O(1)常数阶额外只需要固定数量空间这类算法也叫原地算法。2.O(logN)对数阶额外空间随输入规模对数增长。3.O(N)线性阶额外空间随输入规模线性增长。4.O(N^2)平方阶一般二维数组才会出现。5.2 经典样例分析样例1O(1) 常数阶int Summation(int N) { int ret 0; int i 1; while (i N) { ret i; i; } return ret; }分析只定义了ret、i两个局部变量变量数量固定和 N 无关。 额外空间是常数级别空间复杂度 S(N)O(1)。样例2LeetCode 189 旋转数组 方案1题目给定数组 nums数组元素向右轮转 k 个位置。 思路循环 k 次每次把数组整体向右移动一位。void rotate(int* nums, int numsSize, int k) { k % numsSize; while(k--) { int tmp nums[numsSize-1]; for(int i numsSize -1; i 0 ;i--) { nums[i] nums[i-1]; } nums[0] tmp; } }时间复杂度T(N)O(N^2)多层循环大数据量会超时无法 AC空间复杂度S(N)O(1)仅用了临时变量tmp原地修改数组样例3LeetCode 189 旋转数组 方案2 空间换时间思路开辟临时数组tmp先保存后 k 个元素再移动原数组元素最后拷贝回原数组。void rotate(int* nums, int numsSize, int k){ k % numsSize; if(k 0) return; int tmp[k]; // 变长数组大小k int j 0; // 拷贝后k个元素到tmp for(int i numsSize-k; i numsSize; i) tmp[j] nums[i]; // 前n-k个元素向后挪k位 for(int i numsSize-k-1; i 0; --i) nums[ik] nums[i]; // 把tmp放回数组头部 for(int i 0; i k; i) nums[i] tmp[i]; }时间三次循环一共访问 N 个元素T(N)O(N)空间额外数组tmp[k]数组长度等于 kS(N)O(k)样例4旋转数组【三次反转法】void reverse(int* a, int left, int right) { while(left right) { int tmp a[left]; a[left] a[right]; a[right] tmp; left; --right; } } void rotate(int* nums, int numsSize, int k){ k % numsSize; reverse(nums, 0, numsSize-1); // 整体反转 reverse(nums, 0, k-1); // 前k个反转 reverse(nums, k, numsSize-1); // 后n-k个反转 }举个例子reverse (arr,0,2)对[7,6,5,4,3,2,1]前 3 个反转7,6,5→ 变成5,6,7left0right2交换 a [0] 和 a [2] → 5,6,7left 变成 1right 变成 1循环结束 一段 m 个元素reverse 只需要交换 m/2 次比如 7 个元素交换 3 次4 个元素交换 2 次。不管多少个元素reverse 这段区间的时间复杂度是 O(m)。再将目标对准题目这段代码总交换次数所有操作加起来总共遍历一遍数组里所有元素简单大白话数组越大需要做的操作跟着等比例变多线性复杂度 O (n)因此时间复杂度就是空间复杂度只有局部临时变量tmp常数空间不开新数组→样例5递归阶乘Faclong long Fac(size_t N){ if (N 0) return 1; return Fac(N - 1) * N; }时间复杂度O(N)要算 Fac(N)需要依次调用一共N 层递归调用每层做常数次运算所以T(N)O(N)。空间复杂度O(N)递归的空间消耗在函数调用栈栈帧上不是堆不是 malloc。调用Fac(5)栈Fac(5)调用Fac(4)栈Fac(5), Fac(4)调用Fac(3)栈Fac(5), Fac(4), Fac(3)调用Fac(2)栈Fac(5), Fac(4), Fac(3), Fac(2)调用Fac(1)栈Fac(5), Fac(4), Fac(3), Fac(2), Fac(1)调用Fac(0)触发终止条件 return 1栈Fac(5), Fac(4), Fac(3), Fac(2), Fac(1), Fac(0) 此时栈里同时存在 N1 个函数栈帧。 每一层栈帧都要占用栈内存保存参数 N、返回地址等。等 Fac (0) 返回之后栈才一层一层销毁逐层出栈。最大同时占用的栈帧数 N1和 N 成正比。 所以空间复杂度 O(N)。