第一讲 基本概念
1.1什么是数据结构
1.1.1 关于数据组织--例：图书摆放
例：如何在书架上摆放图书？
| 乱放 | 按拼音顺序放 | 先分类再按拼音顺序 |
| 不方便查 | 二分查找 | 先定类别，再二分查找（方便插入取出） |
- 空间要如何分配？
- 类别要分多细比较好？
解决问题的效率和数据的组织形式相关
1.1.2 关于空间利用--例：print函数实现
例2：函数PrintN,使得能传入一个正整数N后，能顺序打印从1到N的全部正整数
#include<stdio.h>
void PrintN(int N);
int main()
{ int N;scanf("%d",&N);PrintN(N);return 0;
}| 循环实现 | 递归实现 |
| 输入10000可以运行完 | 输入10000罢工了（空间占用很大） |
| |
递归与循环是编程中两种基本的控制结构，适用于不同场景，各有优缺点。以下是它们的对比分析及适用建议：
1. 递归（Recursion）
定义
函数直接或间接调用自身，通过分解问题为更小的子问题来解决原问题。
优点
代码简洁：天然适合分治、树/图遍历等结构清晰的问题（如快速排序、二叉树遍历）。
逻辑直观：直接映射问题本身的数学定义（如阶乘、斐波那契数列）。
缺点
栈溢出风险：递归深度过大时（如处理大规模数据），可能导致栈空间耗尽。
重复计算：某些问题（如朴素斐波那契递归）会重复计算相同子问题，效率低下。
空间复杂度高：需保存每次递归调用的上下文，空间复杂度通常为 O(递归深度)。
适用场景
分治算法（归并排序、快速排序）。
树/图的遍历（前序、中序、后序遍历）。
动态规划问题的递归定义（需结合记忆化优化）。
优化技巧
尾递归优化：将递归调用置于函数末尾，部分编译器可将其转换为循环（如Scheme、ES6）。
记忆化（Memoization）：缓存已计算结果，避免重复计算（如斐波那契数列优化）。
2. 循环（Loop）
定义
通过迭代重复执行代码块，使用
for、while等结构实现。优点
高效性：无函数调用开销，执行速度快。
低空间复杂度：通常只需常量额外空间（如遍历数组时空间复杂度为 O(1)）。
可控性：无栈溢出风险，适合处理大规模数据。
缺点
代码复杂度高：处理递归型问题（如树遍历）时需手动维护栈结构，代码冗长。
逻辑不够直观：某些问题（如汉诺塔）的循环实现可能难以直接映射问题逻辑。
适用场景
线性数据结构的遍历（数组、链表）。
需要严格性能优化的场景（如大规模数据处理）。
内存受限环境（如嵌入式系统）。
3. 时间复杂度与空间复杂度对比
斐波那契数列
递归（无优化）：
时间复杂度：O(2ⁿ)（指数级，重复计算严重）。
空间复杂度：O(n)（递归栈深度）。
循环/迭代：
时间复杂度：O(n)（线性遍历）。
空间复杂度：O(1)（仅需保存前两个值）。
阶乘计算
递归：
时间复杂度：O(n)。
空间复杂度：O(n)（递归栈深度）。
循环：
时间复杂度：O(n)。
空间复杂度：O(1)。
二叉树遍历
递归：
时间复杂度：O(n)。
空间复杂度：O(h)（h为树高，平均O(log n)，最坏O(n)）。
循环（手动栈）：
时间复杂度：O(n)。
空间复杂度：O(h)（与递归相同）。
4. 如何选择递归或循环？
考量因素
选择递归
选择循环
问题结构
分治、树形结构等自然递归问题
线性操作或需严格避免栈溢出
代码可读性
逻辑清晰，代码简洁
需手动管理状态，代码较复杂
性能要求
小规模数据或允许一定性能损失
大规模数据或需极致优化
内存限制
递归深度可控（如树高较低）
内存受限环境（如嵌入式系统）
语言特性
支持尾递归优化（如Scheme、Kotlin）
所有编程语言均原生支持
5. 总结
递归：适合问题结构清晰、子问题独立且规模较小的场景，代码简洁但需警惕栈溢出和重复计算。
循环：适合性能敏感、内存受限或问题结构线性的场景，代码稍复杂但资源占用可控。
最佳实践：
优先用循环处理大规模数据或性能关键代码。
对树、图等递归结构优先用递归实现，必要时优化为循环。
结合记忆化或尾递归优化提升递归效率。
1.1.3关于算法效率--例：计算多项式的值
例3：写程序计算给定多项式在给定点x处解决问题的效率和空间的利用效率相关的值f(x)=a0+a1x+.....+a(n-1)x^(n-1)+anx^n
| 优化前 | 优化后 |
| f(x)=a0+a1x+.....+a(n-1)x^(n-1)+anx^n | f(x)=a0+x(a1+x(...(an-1+xn))...)) |
| |
| 时间长 | 时间短 |
测速：
- clock():捕捉从程序开始运行到clock被调用时所耗费的时间。单位：clock tick（时钟打点）
- 常数CLK_TIK:机器时钟每秒所走的打点数
-
#include<stdio.h> #incluede<time.h>clock_t start,stop; /*clock_t是clock()函数返回的变量类型*/ double duration; /*记录被测函数的运行时间，以秒为单位*/ int main() {/*不在测试范围内的准备工作写在clock调用之前*/start=clock();/*开始计时*/MyFunction();/*被测函数加在这里*/stop=clock();/*停止计时*/duration=((double(stop-start))/CLK_TCK;/*计算运行时间*/ /*其他不在测试范围的处理写在后面，例如输出duration的值*/return 0; }运行时间太短测不出来？
-
让被测函数重复运行充分多次，使得测出的总时间打点间隔充分长，最后计算被测函数的平均运行时间即可。
解决问题的效率和算法的巧妙程度相关
1.1.4抽象数据类型
所以到底什么是数据结构？
- 数据对象在计算机中的组织方式：
- 逻辑结构[线性结构(一对一））；树型结构（一对多）；图（多对多）]
- 物理存储结构：在内存里面的方法（数组、链表...）
- 数据对象必定与一系列加在其上的操作相关联
- 完成这些操作所用的方法叫做算法
抽象数据类型
- 数据类型
- 数据对象集
- 数据集合相关联的操作集
- 抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言均无关
- 只描述数据对象和相关操作集“是什么”，并不涉及“如何做到”的问题
例：“矩阵”抽象数据类型定义
- 类型名称：矩阵（Matrix)
- 数据对象集：……（不关心存储方式：二维数组？一维数组？十字链表？）
- 操作集：加法……（不关心先按行加？先按列加？什么语言？）
1.2 什么是算法
1.2.1算法的定义
- 算法（Algorithm)
- 一个有限指令集
- 接受一些输入（有些情况不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能处理的范围之内
- 描述应不依赖于任何一种计算机语言以及具体的实现手段
例1：选择排序算法的伪码描述
void Selectionsort(int list[],int N)
{/*将N个整数List[0]...List[N-1]进行非递减排序*/for(i=0;i<N;i++){MinPosition=SocanFormin(List,i,N-1);/*从List[i]到List[N-1]找最小元，并将其位置给MinPosition*/ Swap([List[i],List[MinPosition]);/*将末排序部分的最小元换到有序部分的最后位置*/}
}抽象--
- List到底是数组还是链表（虽然看起来很像数组）？不考虑
- Swap用函数还是用宏去实现？不考虑
1.2.2 什么是好的算法？
- 空间复杂度S（n)
- 时间复杂度T（n）
时间和空间复杂度是评估算法效率的两个重要指标：
时间复杂度 T(n)
定义：算法执行所需时间与输入规模 n 的关系。
分析方法：
基本操作：找出执行最频繁的操作（如循环、条件判断）。
循环结构：
单层循环：O(n)。
嵌套循环：O(n²)（若两层都与 n 相关）。
可变步长（如二分）：O(log n)。
递归算法：
通过递归方程（如 T(n) = a·T(n/b) + f(n)）应用主定理。
例子：归并排序的时间复杂度为 O(n log n)。
分治策略：总时间由子问题数量和合并操作决定。
空间复杂度 S(n)
定义：算法运行中临时占用的存储空间与 n 的关系。
分析方法：
固定空间：变量、常量占用 O(1)。
动态空间：
数组/链表：O(n)。
矩阵：O(n²)。
递归调用：
空间复杂度取决于递归深度（如斐波那契数列为 O(n)）。
尾递归优化可减少栈空间（如 O(1)）。
示例对比
算法
时间复杂度 T(n)
空间复杂度 S(n)
冒泡排序
O(n²)
O(1)
快速排序
O(n log n) 平均
O(log n) 平均（递归栈）
归并排序
O(n log n)
O(n)（额外数组）
二分查找
O(log n)
O(1)
斐波那契递归
O(2ⁿ)
O(n)（递归深度）
总结
时间复杂度关注操作次数的增长趋势。
空间复杂度关注运行时的最大额外存储需求。
关键点：忽略低阶项和常数系数，分析最坏/平均情况，递归深度决定空间复杂度。
通过系统分析算法结构（循环、递归、动态分配等），结合大 O 表示法规则，可准确推导复杂度。
例：
void PrintN(int N)
{if(N){Print(N-1);printf("%d\n",N);}return;
}S（n)=C(常数）*N
递归占用空间和N成正比，但是循环占用的空间是固定的，无论N多大
| f(x)=a0+a1x+.....+a(n-1)x^(n-1)+anx^n | f(x)=a0+x(a1+x(...(an-1+xn))...)) |
| |
| （1+2+……+n)={n^2+n)次乘法 | n次乘法 |
| T(n)=C2n^2+C1n | T(n)=Cn |
什么是好算法？
- 在分析一般算法的效率时，我们经常关注下面 两种复杂度
- 最坏情况复杂度 Tworst( n )
- 平均复杂度 Tavg( n )
- Tavg( n ) ≤ Tworst( n )
复杂度的渐进表示法
- T(n) = O(f(n)) 表示存在常数C >0, n0>0 使得当 n≥n0 时有T(n) ≤ Cf· (n)
- T(n) = Ω(g(n)) 表示存在常数C >0, n0>0 使得当 n≥n0 时有T(n) ≥ C·g(n)
- T(n) = Θ(h(n)) 表示同时有T(n) = O(h(n)) 和 T(n) = Ω(h(n))
复杂度分析小窍门
- 若两段算法分别有复杂度T1(n) = O(f1(n)) 和T2(n) = O(f2(n))，则
- T1(n) + T2(n) = max( O(f1(n)), O(f2(n)) )
- T1(n) × T2(n) = O(f1(n) × f2(n) ) n
- 若T(n)是关于n 的k阶多项式，那么T(n)=Θ(nk) n
- 一个for循环的时间复杂度等于循环次数乘以循环体
- 代码的复杂度 n if-else 结构的复杂度取决于if的条件判断复杂度 和两个分枝部分的复杂度，总体复杂度取三者中最大
1.3 应用实例：最大子列和问题
给定N个整数的序 { A1, A2, …, AN}， 求函数 f (i , j) = max{0 , Ak } 的最大值。
算法1&算法2
算法1
int MaxSubseqSum1( int A[], int N )
{ int ThisSum, MaxSum = 0;
int i, j, k;for( i = 0; i < N; i++ ) { /* i是子列左端位置 */for( j = i; j < N; j++ ) { /* j是子列右端位置 */ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */ for( k = i; k <= j; k++ )ThisSum += A[k];if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */MaxSum = ThisSum; /* 则更新结果 */} /* j循环结束 */} /* i循环结束 */
return MaxSum;
} - T( N ) = O( N3 )
算法2
int MaxSubseqSum2( int A[], int N )
{ int ThisSum, MaxSum = 0;int i, j;for( i = 0; i < N; i++ ) { /* i是子列左端位置 */ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */ for( j = i; j < N; j++ ) { /* j是子列右端位置 */ThisSum += A[j];/*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/ if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */MaxSum = ThisSum; /* 则更新结果 */} /* j循环结束 */} /* i循环结束 */return MaxSum;
} - T( N ) = O( N2 )
算法3：分而治之
T ( N ) = 2 T( N/2 ) + c N , T(1) = O(1)
= 2 [2 T( N/2^2 ) + c N/2] + c N
= 2^k O(1) + c k N 其中 N/2^k = 1
= O( Nlog N )
分而治之（Divide and Conquer）
分而治之是一种经典的算法设计策略，核心思想是将复杂问题分解为多个子问题，递归解决子问题后合并结果，最终得到原问题的解。其高效性体现在通过分解降低问题难度，常用于排序、搜索、数学计算等领域。
分治法的三个核心步骤
分解（Divide）
将原问题划分为若干个规模较小、结构相同的子问题。
示例：归并排序中将数组分成两个子数组。解决（Conquer）
递归解决子问题。若子问题规模足够小，直接求解（递归终止条件）。
示例：快速排序中对长度 1 的数组直接返回。合并（Combine）
将子问题的解合并为原问题的解。
示例：归并排序中合并两个有序子数组。
时间复杂度 T(n) 分析
分治法的时间复杂度通常通过递归方程建模，结合主定理（Master Theorem） 求解。
经典分治算法的时间复杂度
算法
递归方程
时间复杂度
归并排序
T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)
O(n \log n)O(nlogn)
快速排序
T(n) = T(k) + T(n-k) + O(n)T(n)=T(k)+T(n−k)+O(n)
平均 O(n \log n)O(nlogn)
二分查找
T(n) = T(n/2) + O(1)T(n)=T(n/2)+O(1)
O(\log n)O(logn)
汉诺塔问题
T(n) = 2T(n-1) + O(1)T(n)=2T(n−1)+O(1)
O(2^n)O(2n)
空间复杂度 S(n) 分析
分治法的空间复杂度主要由两部分决定：
递归调用栈的深度：取决于分解次数（如二叉树高度 \log nlogn）。
合并时的额外空间：如归并排序需 O(n)O(n) 的临时数组。
示例对比
算法
空间复杂度 S(n)
原因
归并排序
O(n)O(n)
合并时需要额外数组
快速排序
O(\log n)O(logn)（平均）
递归栈深度（取决于分区均衡性）
二分查找
O(1)O(1)（迭代）或 O(\log n)O(logn)（递归）
递归栈深度或固定变量
Strassen矩阵乘法
O(\log n)O(logn)
递归调用栈
分治法的典型应用
排序与搜索
归并排序：稳定排序，时间复杂度 O(n \log n)O(nlogn)。
快速排序：原地排序，平均时间复杂度 O(n \log n)O(nlogn)。
二分查找：在有序数组中高效搜索，时间复杂度 O(\log n)O(logn)。
数学计算
大整数乘法（Karatsuba算法）：将乘法分解为更小规模的加减运算，复杂度 O(n^{\log_2 3}) \approx O(n^{1.585})O(nlog23)≈O(n1.585)。
矩阵乘法（Strassen算法）：通过减少乘法次数优化计算，复杂度 O(n^{\log_2 7}) \approx O(n^{2.807})O(nlog27)≈O(n2.807)。
几何问题
最近点对问题：将平面点集分治处理，合并时检查边界区域，复杂度 O(n \log n)O(nlogn)。
分治法 vs 动态规划 vs 贪心算法
策略
核心思想
适用场景
子问题性质
分治法
分解 → 解决 → 合并
子问题独立，结构相同
无重叠
动态规划
记忆化子问题，避免重复计算
子问题重叠，有最优子结构
重叠且需记录中间结果
贪心算法
局部最优选择推进全局最优解
问题具有贪心选择性质
无回溯
分治法的优缺点
优点
高效性：通过递归降低问题规模，显著减少计算量（如归并排序比冒泡排序快）。
并行潜力：子问题相互独立，适合多线程或分布式计算。
缺点
递归开销：递归调用可能增加时间与空间成本。
合并复杂性：某些问题的合并步骤设计困难（如汉诺塔问题）。
空间占用：某些场景需额外存储空间（如归并排序的 O(n)O(n) 空间）。
总结
分而治之通过递归分解问题与高效合并结果，在排序、搜索、数学计算等领域广泛应用。其复杂度分析需结合主定理与递归树方法，重点关注：
时间：子问题数量、规模及合并成本。
空间：递归深度与合并时的额外存储需求。
掌握分治法需熟练设计分解策略与合并逻辑，并权衡其效率与实现复杂度。
算法4：在线处理
int MaxSubseqSum4( int A[], int N )
{ int ThisSum, MaxSum;int i;ThisSum = MaxSum = 0;for( i = 0; i < N; i++ ) {ThisSum += A[i]; /* 向右累加 */if( ThisSum > MaxSum )MaxSum = ThisSum; /* 发现更大和则更新当前结果 */ else if( ThisSum < 0 ) /* 如果当前子列和为负 */ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */ }return MaxSum;
} 在线处理（Online Algorithm）是一种逐项处理输入数据的算法策略，其核心特点是无需预先获取全部输入，每处理一个数据项就能给出当前的最优解或部分结果。这种特性使其适用于实时数据流、大规模数据或内存受限的场景。
在线处理的核心特点
逐项处理：数据逐个到达，处理完一个后立即丢弃（不存储全部历史数据）。
实时性：每一步处理后都能给出当前结果。
低空间占用：通常不需要存储完整输入，空间复杂度较低。
时间复杂度 T(n) 分析
在线处理算法的时间复杂度通常是线性的（O(n)），因为每个数据项仅被处理一次。但具体复杂度取决于每步操作：
简单操作（如累加、比较）：每步 O(1)，总时间 O(n)。
复杂维护（如动态插入有序结构）：每步 O(log k)（k 为当前数据量），总时间 O(n log k)。
示例
最大子序和（Kadane 算法）
每步更新当前子数组和的最大值，时间复杂度 O(n)，空间复杂度 O(1)。
滑动窗口最大值
使用双端队列维护窗口内最大值，每步均摊 O(1)，总时间 O(n)。
空间复杂度 S(n) 分析
在线处理算法的空间复杂度通常较低，仅需存储少量中间状态：
固定窗口大小：如滑动窗口算法，空间复杂度 O(k)（k 为窗口长度）。
无窗口限制：若仅需维护聚合值（如总和、极值），空间复杂度 O(1)。
示例
算法
时间复杂度 T(n)
空间复杂度 S(n)
实时数据流求和
O(n)
O(1)
滑动窗口中位数
O(n log k)
O(k)
在线统计出现频率
O(n)
O(m)（m 为唯一值数量）
在线处理 vs 离线处理
特性
在线处理
离线处理
输入可见性
逐项到达，无法预知未来
全部输入已知
延迟要求
实时输出结果
可等待全部数据后处理
空间复杂度
通常 O(1) 或 O(k)
可能需 O(n) 存储全部数据
最优性
可能是次优解
可找到全局最优解
典型应用场景
实时数据流
股票价格监控、传感器数据处理。
内存受限环境
无法存储大规模数据（如嵌入式系统）。
动态决策系统
自动驾驶、实时推荐系统。
设计在线处理算法的关键
维护中间状态：用最少的内存记录关键信息（如最大值、总和）。
增量更新：新数据到达时，仅更新相关状态，避免重新计算。
取舍权衡：在实时性和最优性之间平衡（如允许近似解）。
总结
在线处理通过逐项处理数据和低空间占用，在实时性和资源效率之间取得平衡。其复杂度分析需重点关注：
时间：每步操作的效率（通常 O(1) 或 O(log k)）。
空间：中间状态的存储需求（通常与数据规模无关）。