408考研数据结构复习（绪论及算法时间复杂度）
文章目录 总结
前言
最近在复习408课程，感觉每次复习完再写一篇博客可能会记忆更深刻些，因此萌生了这样的想法，可能会有些错误之处，欢迎指正。（参考书为王道考研数据结构和严蔚敏教授的《数据结构》）
先复习数据结构第一章 绪论（有关算法的知识点，不作为考点的知识点有些就不写进来了，有需要请查阅相关资料）
一、什么是数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构（）。数据结构由三个部分的内容组成：
1.逻辑结构
（1）集合（包含关系）
（2）线性结构（一对一关系）
（3）树形结构（一对多关系）
（4）图状或网状结构（多对多关系）
2.存储结构（又叫物理结构）
（1）顺序存储：逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。★优点是可以实现随机存储；
缺点是会产生较多的外部碎片。
（2）链式存储：逻辑上相邻的元素可以存储在物理位置上不相邻的存储单元中。
优点是可以充分利用所有的存储单元；
★缺点是存储指针会占用额外的空间造成空间的过分利用，而且只能顺序存取。
（3）索引存储：附加建立索引表，每个索引表项对应着一个关键字和地址。★优点是检索速度快；
★缺点是附加表现消耗额外空间。并且增删数据时也要修改索引表，比较麻烦。
（4）散列存储：根据元素的关键字通过散列函数计算出该元素的存储地址。
★优点是检索、增删结点都很快；
★缺点是该存储取决于散列函数的选择，到后面学到查找的时候会详细介绍散列函数会造成冲突，而解决冲突会增加时间和空间的开销。关于散列函数的有关性质和密码学也有一定的关系，有兴趣的uu可以搜一搜看看。
3.数据的运算
运算的定义是针对逻辑结构的，指出运算的功能；
运算的实现是针对存储结构的，指出运算的具体操作步骤。
个人错题总结：
01.可以用（D）定义一个完整的数据结构。
A.数据元素 B.数据对象 C.数据关系 D.抽象数据类型
解答：抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而构成一个完整的数据结构的定义。
二、算法的介绍和算法的时间复杂度 1.算法的基本概念
算法（）是对于某些特定的问题的求解的过程的描述，它是一种有限的指令序列。
★2.算法的特性
（1）有穷性：①有限步骤；②有限时间。
（2）确定性：对于确定的输入只有一个确定的输出。
（3）可行性：可以通过已经实现的基本运行执行有限次数来实现算法。
（4）零个或多个输入
（5）一个或多个输出
★★★3.算法的时间复杂度
算法中所有语句的频度之和记为T(n)。
时间复杂度主要分析的是T(n)的数量级，通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此算法的时间复杂度记为：
T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))
式中，O的含义是T(n)的数量级，数学定义是：若T(n)和f(n)是定义在正整数集合上的俩个函数，则存在正常数C和n0，使得当n≥n0时，都满足0≤T(n)≤Cf(n)。
其他的一些关于时间复杂度的表示有Ω和θ，其他对于算法例如
T ( n ) = { 1 , n = 1 a T ( n / b ) + f ( n ) , n > 1 ; T(n)=\begin{cases} 1,\quad n=1 \\\\ aT(n/b)+f(n),\quad n>1; \end{cases} T(n)=⎩⎨⎧1,n=1aT(n/b)+f(n),n>1;
这样的形式(a≥1，b≥1)，可以参考主定理来求此类算法的时间复杂度。也可以用下面特殊情况的小结论做一些大题的算法分析时可以直接写出该算法的时间复杂度。
若f(n)=cn，c≥1，
当a 当a=b的时候，T(n)=O(nlogn)
当a>b的时候，T(n)=O(n^(logba))
时间复杂度的计算遵循以下规则：
T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)));
T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n));
此外，一些常见的复杂度需要记忆：
O(1)2n)2n)2)3) 1 ; T(n)=\begin{cases} 1,\quad n=1 \\\\ 2T(n/2)+n,\quad n>1; \end{cases} T(n)=⎩⎨⎧1,n=12T(n/2)+n,n>1;
式中，n是问题的规模，为简单起见，设n是2的整数次幂。
解答：
由题意得，n=2α。
①T(2α)=2T(2α-1)+2α
②T(2α-1)=2T(2α-2)+2α-1
③T(2α-2)=2T(2α-3)+2α-2
将②式代入①式得，
T(2α)=22T(2α-2)+2×2α
将③式也代入得，
T(2α)=23T（2α-3）+3×2α
由此可得，
T(2α)=2αT(1)+α×2α=(α+1)2α，此时，把n=2α还原(α=log2n),可得
T(n)=2^(log2n)+=n(log2n+1),也就是O()。
当然，也可以运用主定理来求解，
分析a=2,b=2，基准函数是Θ(n^(log22))也就是Θ(n),因为n=f(n)，根据主定理可得，O(n)=。
总结
本章的重点是分析程序的时间复杂度。注意在递归程序中一般使用公式进行递推。有时间的uu可以多留意留意主定理相关的内容，相信对于后面的各种排序或者查找算法计算其时间复杂度的时候会有帮助的，当作拓展看看也是可以的。另外，在算法分析中，一般logn默认为以2为底数。算法的空间复杂度较为复杂就不多赘述。
下期预告：第二章 线性表（由于最近在复习计组，第二章内容较多可能需要有俩三天才发）
