计算机 408 · 数据结构第 1 章「绪论」学习笔记[!NOTE]本章看起来概念多真正的主线只有两条数据怎样组织以及算法要花多少时间和空间。复杂度是后面所有算法比较的共同语言。学习进度能区分逻辑结构、存储结构和数据运算能区分数据类型与抽象数据类型 ADT能判断算法的时间、空间复杂度能分析常见循环和递归程序0. 全章地图现实问题 ↓ 抽象 数据元素 元素之间的关系 可执行的操作 ↓ 逻辑结构想怎样组织 ↓ 映射到计算机 存储结构实际怎样存 ↓ 算法怎样处理 → 时间复杂度 空间复杂度1. 数据结构的基本概念1.1 基本术语术语白话理解例子数据能被计算机识别和处理的信息数字、字符、图像数据元素数据的基本单位一名学生、一条记录数据项构成数据元素的最小单位学号、姓名数据对象性质相同的数据元素集合全体学生记录数据类型值的集合以及允许的操作int及加减乘除抽象数据类型 ADT只说明数据对象、关系和操作不规定实现“栈”只规定后进先出ADT 强调“能做什么”具体存储结构强调“怎样做到”。同一个线性表既可以用数组实现也可以用链表实现。1.2 数据结构的三要素逻辑结构元素之间在问题中的关系。存储结构逻辑关系在计算机中的表示。数据运算定义在结构上的增、删、查、改等操作。逻辑结构类型元素关系后续章节集合除同属一个集合外无明显关系散列表、并查集线性结构一对一线性表、栈、队列、串树形结构一对多树、二叉树、B 树图状结构多对多图存储结构类型特点典型结构顺序存储逻辑相邻的元素物理上也相邻数组、顺序表链式存储用指针表示逻辑关系链表、邻接表索引存储额外建立索引表索引查找、B 树散列存储根据关键字计算地址Hash 表[!WARNING]顺序、链式、索引、散列是存储结构线性、树、图是逻辑结构。选择题经常故意混在一起。2. 算法与算法评价2.1 好算法的基本要求算法通常具有有穷性、确定性、可行性、输入和输出。评价算法时还关注正确性、可读性、健壮性和效率。有穷性有限步骤后必须结束只针对算法。程序可以长期运行例如操作系统服务进程。确定性同样输入在每一步的含义明确。2.2 渐进复杂度当输入规模n很大时只保留增长最快的部分3n² 10n 8 O(n²) log₂n、log₁₀n 在大 O 下都写 O(log n)常见增长速度O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)2.3 循环复杂度分析固定模板找基本操作 → 看它执行多少次 → 只保留最高阶。for(i0;in;i)// n 次x;// O(n)for(i1;in;i*2)// 1,2,4,...x;// O(log n)for(i0;in;i)for(j0;ji;j)x;// 01...(n-1)O(n²)若循环变量按i i * k增长通常求解k^t n得到t O(log n)。2.4 递归复杂度常见递推递推式复杂度典型算法T(n)T(n-1)O(1)O(n)线性递归T(n)T(n/2)O(1)O(log n)折半查找T(n)2T(n/2)O(n)O(n log n)归并排序T(n)T(n-1)O(n)O(n²)快排最坏情形[!TIP]408 计算复杂度时不只看循环层数。循环边界若依赖另一个变量应先写出总执行次数的求和式。3. 空间复杂度空间复杂度关注额外辅助空间通常不计输入本身占用的空间。原地算法辅助空间为O(1)。长度为n的辅助数组O(n)。递归深度为n调用栈通常为O(n)。分治递归深度为log n若每层只用常数空间栈空间为O(log n)。4. 408 高频考点补充必考判断算法的时间复杂度与机器速度、编程语言无关但具体运行时间有关。同一逻辑结构可采用不同存储结构。存储结构会影响运算效率但不会改变逻辑关系的定义。最坏、最好、平均复杂度必须明确输入分布或状态。解题模板1. 明确输入规模 n 表示什么 2. 找到执行次数最多的基本操作 3. 写出次数或求和式 4. 去掉常数、低阶项和系数 5. 递归算法另外分析递归深度和栈空间5. 高频易错点易错点正确理解O(n)表示一定执行 n 次大 O 表示渐进上界不是精确次数两层循环必为O(n²)取决于边界和变量变化方式递归算法空间一定是O(1)递归调用栈也占空间数据项等于数据元素数据项是数据元素的组成部分ADT 规定具体数组或指针ADT 只规定逻辑和操作接口6. 轻量自测图的邻接表属于逻辑结构还是存储结构循环变量从 1 开始每次乘 3直到超过n复杂度是多少T(n)T(n/2)O(1)的时间复杂度是多少递归栈空间通常是多少为什么3n²n和100n²都属于O(n²)展开答案存储结构它是图这种逻辑结构的一种实现。O(log n)。时间O(log n)若每层使用常数空间则栈空间也是O(log n)。渐进分析只关注最高阶增长趋势忽略常数系数与低阶项。7. 最终记忆卡片数据结构三要素逻辑结构 存储结构 数据运算 逻辑结构集合、线性、树形、图状 存储结构顺序、链式、索引、散列 复杂度找基本操作的执行次数只保留最高阶 递归别忘调用栈空间复习日志日期学习内容能否脱稿讲解仍然困惑的点加深理解把“数据结构”拆成三个问题1. 一个学生管理系统的例子假设系统要保存学生的学号、姓名和成绩并支持“按学号查找”和“按成绩排序”数据元素一个学生记录 数据项学号、姓名、成绩 逻辑结构所有学生组成线性表 存储结构顺序表、链表或散列表 数据运算插入、删除、查找、排序题目问“学生记录之间是一对一的前后关系”回答的是逻辑结构题目问“记录是否连续存放”回答的是存储结构题目问“如何快速找到学号”回答的是运算和算法。2. ADT 为什么重要栈的 ADT 可以写成数据对象有限个同类型元素 关系元素按进入顺序排列 操作InitStack、Push、Pop、GetTop、StackEmpty它没有规定栈必须用数组还是链表。这样做的好处是上层程序只依赖接口底层实现可以更换。408 题目常把“逻辑描述”和“实现细节”放在同一个选项中看到具体数组下标时就已经进入存储结构层面。3. O、Ω、Θ 的区别符号含义直观理解O(g(n))渐进上界不会比g(n)增长得更快Ω(g(n))渐进下界至少和g(n)同阶Θ(g(n))同阶紧确界上界和下界都是g(n)例如3n²2n1同时属于O(n²)、Ω(n²)和Θ(n²)。考试问“时间复杂度”时通常写紧确阶Θ(n²)教材和代码题中也常简写为O(n²)。4. 复杂度推导示例for(i1;in;i)for(j1;ji;j)count;count执行次数是12...nn(n1)/2所以为Θ(n²)。i1;while(in){j1;while(ji)j*2;i*2;}外层执行Θ(log n)次第t次外层中i2^t内层执行Θ(t)次总次数为ΣtΘ((log n)²)不是简单的Θ(log n)。递归例子F(n)F(n/2)1每次把规模减半递归深度为log₂n因此时间和栈空间都是Θ(log n)。若是F(n)F(n-1)F(n-2)递归树会指数增长朴素实现约为Θ(2^n)。5. 复杂度分析的解题思路n到底表示元素个数、边数、树高还是关键字位数循环变量是加 1、乘 2还是依赖另一个变量多个循环是相加还是相乘嵌套循环通常相乘前后顺序执行通常相加。递归是否共享子问题重复计算会让复杂度从线性变成指数。是否把输入数组本身误算进辅助空间空间复杂度通常只计算额外空间。
计算机 408 · 数据结构 · 绪论
计算机 408 · 数据结构第 1 章「绪论」学习笔记[!NOTE]本章看起来概念多真正的主线只有两条数据怎样组织以及算法要花多少时间和空间。复杂度是后面所有算法比较的共同语言。学习进度能区分逻辑结构、存储结构和数据运算能区分数据类型与抽象数据类型 ADT能判断算法的时间、空间复杂度能分析常见循环和递归程序0. 全章地图现实问题 ↓ 抽象 数据元素 元素之间的关系 可执行的操作 ↓ 逻辑结构想怎样组织 ↓ 映射到计算机 存储结构实际怎样存 ↓ 算法怎样处理 → 时间复杂度 空间复杂度1. 数据结构的基本概念1.1 基本术语术语白话理解例子数据能被计算机识别和处理的信息数字、字符、图像数据元素数据的基本单位一名学生、一条记录数据项构成数据元素的最小单位学号、姓名数据对象性质相同的数据元素集合全体学生记录数据类型值的集合以及允许的操作int及加减乘除抽象数据类型 ADT只说明数据对象、关系和操作不规定实现“栈”只规定后进先出ADT 强调“能做什么”具体存储结构强调“怎样做到”。同一个线性表既可以用数组实现也可以用链表实现。1.2 数据结构的三要素逻辑结构元素之间在问题中的关系。存储结构逻辑关系在计算机中的表示。数据运算定义在结构上的增、删、查、改等操作。逻辑结构类型元素关系后续章节集合除同属一个集合外无明显关系散列表、并查集线性结构一对一线性表、栈、队列、串树形结构一对多树、二叉树、B 树图状结构多对多图存储结构类型特点典型结构顺序存储逻辑相邻的元素物理上也相邻数组、顺序表链式存储用指针表示逻辑关系链表、邻接表索引存储额外建立索引表索引查找、B 树散列存储根据关键字计算地址Hash 表[!WARNING]顺序、链式、索引、散列是存储结构线性、树、图是逻辑结构。选择题经常故意混在一起。2. 算法与算法评价2.1 好算法的基本要求算法通常具有有穷性、确定性、可行性、输入和输出。评价算法时还关注正确性、可读性、健壮性和效率。有穷性有限步骤后必须结束只针对算法。程序可以长期运行例如操作系统服务进程。确定性同样输入在每一步的含义明确。2.2 渐进复杂度当输入规模n很大时只保留增长最快的部分3n² 10n 8 O(n²) log₂n、log₁₀n 在大 O 下都写 O(log n)常见增长速度O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)2.3 循环复杂度分析固定模板找基本操作 → 看它执行多少次 → 只保留最高阶。for(i0;in;i)// n 次x;// O(n)for(i1;in;i*2)// 1,2,4,...x;// O(log n)for(i0;in;i)for(j0;ji;j)x;// 01...(n-1)O(n²)若循环变量按i i * k增长通常求解k^t n得到t O(log n)。2.4 递归复杂度常见递推递推式复杂度典型算法T(n)T(n-1)O(1)O(n)线性递归T(n)T(n/2)O(1)O(log n)折半查找T(n)2T(n/2)O(n)O(n log n)归并排序T(n)T(n-1)O(n)O(n²)快排最坏情形[!TIP]408 计算复杂度时不只看循环层数。循环边界若依赖另一个变量应先写出总执行次数的求和式。3. 空间复杂度空间复杂度关注额外辅助空间通常不计输入本身占用的空间。原地算法辅助空间为O(1)。长度为n的辅助数组O(n)。递归深度为n调用栈通常为O(n)。分治递归深度为log n若每层只用常数空间栈空间为O(log n)。4. 408 高频考点补充必考判断算法的时间复杂度与机器速度、编程语言无关但具体运行时间有关。同一逻辑结构可采用不同存储结构。存储结构会影响运算效率但不会改变逻辑关系的定义。最坏、最好、平均复杂度必须明确输入分布或状态。解题模板1. 明确输入规模 n 表示什么 2. 找到执行次数最多的基本操作 3. 写出次数或求和式 4. 去掉常数、低阶项和系数 5. 递归算法另外分析递归深度和栈空间5. 高频易错点易错点正确理解O(n)表示一定执行 n 次大 O 表示渐进上界不是精确次数两层循环必为O(n²)取决于边界和变量变化方式递归算法空间一定是O(1)递归调用栈也占空间数据项等于数据元素数据项是数据元素的组成部分ADT 规定具体数组或指针ADT 只规定逻辑和操作接口6. 轻量自测图的邻接表属于逻辑结构还是存储结构循环变量从 1 开始每次乘 3直到超过n复杂度是多少T(n)T(n/2)O(1)的时间复杂度是多少递归栈空间通常是多少为什么3n²n和100n²都属于O(n²)展开答案存储结构它是图这种逻辑结构的一种实现。O(log n)。时间O(log n)若每层使用常数空间则栈空间也是O(log n)。渐进分析只关注最高阶增长趋势忽略常数系数与低阶项。7. 最终记忆卡片数据结构三要素逻辑结构 存储结构 数据运算 逻辑结构集合、线性、树形、图状 存储结构顺序、链式、索引、散列 复杂度找基本操作的执行次数只保留最高阶 递归别忘调用栈空间复习日志日期学习内容能否脱稿讲解仍然困惑的点加深理解把“数据结构”拆成三个问题1. 一个学生管理系统的例子假设系统要保存学生的学号、姓名和成绩并支持“按学号查找”和“按成绩排序”数据元素一个学生记录 数据项学号、姓名、成绩 逻辑结构所有学生组成线性表 存储结构顺序表、链表或散列表 数据运算插入、删除、查找、排序题目问“学生记录之间是一对一的前后关系”回答的是逻辑结构题目问“记录是否连续存放”回答的是存储结构题目问“如何快速找到学号”回答的是运算和算法。2. ADT 为什么重要栈的 ADT 可以写成数据对象有限个同类型元素 关系元素按进入顺序排列 操作InitStack、Push、Pop、GetTop、StackEmpty它没有规定栈必须用数组还是链表。这样做的好处是上层程序只依赖接口底层实现可以更换。408 题目常把“逻辑描述”和“实现细节”放在同一个选项中看到具体数组下标时就已经进入存储结构层面。3. O、Ω、Θ 的区别符号含义直观理解O(g(n))渐进上界不会比g(n)增长得更快Ω(g(n))渐进下界至少和g(n)同阶Θ(g(n))同阶紧确界上界和下界都是g(n)例如3n²2n1同时属于O(n²)、Ω(n²)和Θ(n²)。考试问“时间复杂度”时通常写紧确阶Θ(n²)教材和代码题中也常简写为O(n²)。4. 复杂度推导示例for(i1;in;i)for(j1;ji;j)count;count执行次数是12...nn(n1)/2所以为Θ(n²)。i1;while(in){j1;while(ji)j*2;i*2;}外层执行Θ(log n)次第t次外层中i2^t内层执行Θ(t)次总次数为ΣtΘ((log n)²)不是简单的Θ(log n)。递归例子F(n)F(n/2)1每次把规模减半递归深度为log₂n因此时间和栈空间都是Θ(log n)。若是F(n)F(n-1)F(n-2)递归树会指数增长朴素实现约为Θ(2^n)。5. 复杂度分析的解题思路n到底表示元素个数、边数、树高还是关键字位数循环变量是加 1、乘 2还是依赖另一个变量多个循环是相加还是相乘嵌套循环通常相乘前后顺序执行通常相加。递归是否共享子问题重复计算会让复杂度从线性变成指数。是否把输入数组本身误算进辅助空间空间复杂度通常只计算额外空间。