数据结构和算法绪论
什么是数据结构？
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关
程序设计 = 数据结构 + 算法
逻辑结构和物理结构
逻辑结构
数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构，数据的逻辑结构分为以下四种：
- 集合结构：集合结构的集合中任何两个数据元素之间都没有逻辑关系，组织形式松散
- 线性结构：数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构
- 树状结构：树状结构是一个或多个节点的有限集合
- 网络结构：网络结构是指通信系统的整体设计，它为网络硬件、软件、协议、存取控制和拓扑提供标准
物理结构（存储结构）
数据的存储结构是指数据的逻辑结构在计算机中的表示。数据的存储结构分为顺序存储结构和链接存储结构两种
- 顺序存储结构：顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构
- 链接存储结构：链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
算法
例：计算从1加到10000的结果
不用算法：
int sum = 0;
for (size_t n = 1; n <= 10000; ++i)
{
sum += n;
}
用算法：
int sum = 0;
sum = 10001 * 10000 / 2
特性
- 输入
- 算法有0个或多个输入
- 输出
- 算法至少有1个或多个输出
- 算法必须有输出
- 有穷性
- 算法在执行有限步骤后，自动结束而不会出现死循环，并且每个步骤在可接受的时间内完成
- 确定性
- 算法的每一个步骤都具有确定的含义，不能出现二义性
- 可行性
- 算法的每一步都必须是可行的
设计要求
- 正确性
- 算法程序没有语法错误
- 算法程序对于合法输入能够产生满足要求的输出
- 算法程序对于非法输入能够产生满足规格的说明
- 算法程序对于故意刁难的测试输入都有满足要求的输出结果
- 可读性
- 算法要便于阅读、理解和交流
- 健壮性
- 当输入数据不合法时，算法也能做出相应处理，而不是崩溃
- 时间效率高和存储量低
时间复杂度和空间复杂度
影响效率的几个方面
-
算法采用的方案
-
编译产生的代码量
-
问题的输入规模
-
机器执行指令的速度
时间复杂度
算法中基本操作重复执行的次数是问题规模\(n\)的某个函数，用\(T(n)\)表示，若有某个辅助函数\(f(n)\),存在一个正常数\(c\)使得\(f(n)c>=T(n)\)恒成立。记作\(T(n)=O(f(n))\),称\(O(f(n))\) 为算法的渐进时间复杂度，简称时间复杂度
思考一个问题，类似 \(2n+1\)、\(2n^2+2n+1\) 这样的频度，还可以再简化吗？答案是肯定的。
以 \(2n+1\) 为例，当 \(n\) 无限大时，是否在 \(2n\) 的基础上再做 +1 操作，并无关紧要，因为 \(2n\) 和 \(2n+1\) 当 \(n\) 无限大时，它们的值是无限接近的。甚至于我们还可以认为，当 \(n\) 无限大时，是否给 \(n\) 乘 2，也是无关紧要的，因为 \(n\) 是无限大，\(2n\) 也是无限大。
再以无限大的思想来简化 \(2n^2+2n+1\)。当 n 无限大的：
首先，常数 1 是可以忽略不计的；
其次，对于指数级的 \(2n^2\) 来说，是否在其基础上加 \(2n\)，并无关紧要；
甚至于，对于是否给 \(n^2\) 乘 2，也可以忽略。
因此，最终频度 \(2n^2+2n+1\) 可以简化为 \(n^2\) ，也就是时间复杂度为\(O(n^2)\)
\(O(1)\) \(<\) \(O(logn)\) \(<\) \(O(n)\) \(<\) \(O(nlog)\) \(<\) \(O(n^2)\) \(<\) \(O(n^3)\) \(<\) \(O(2^n)\) \(<\) \(O(n!)\) \(<\) \(O(n^n)\)
空间复杂度
如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 \(O(1)\)；反之，如果有关，则需要进一步判断它们之间的关系：
- 如果随着输入值 \(n\) 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 \(O(n)\) 表示;
- 如果随着输入值 \(n\) 的增大，程序申请的临时空间成 \(n^2\) 关系增长，则程序的空间复杂度用 \(O(n^2)\) 表示；
- 如果随着输入值 \(n\) 的增大，程序申请的临时空间成 \(n^3\) 关系增长，则程序的空间复杂度用 \(O(n^3)\) 表示