数据结构note（一）
1.1 什么是数据结构？
“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数给出。”——Sartaj Sahni.
-
解决问题方法的效率，跟数据的组织方式有关
-
解决问题方法的效率，跟空间的利用效率有关
-
解决问题方法的效率，跟算法的巧妙程度有关
抽象数据类型
-
数据结构（比如C++里的class）：
-
数据对象集
-
数据集合相关联的操作集
-
-
抽象：
-
与存放数据的机器无关
-
与数据存储的物理结构无关
-
与实现操作的算法和编程语言均无关
-
1.2 什么是算法？
-
一个有限的指令集
-
接受一些输入（或不需要）
-
产生输出
-
在有限步骤后终止
-
每条指令必须
-
有充分明确的目标，不可以有歧义
-
计算机的处理能力范围内
-
描述不依赖计算机语言和具体实现手段
-
什么是好的算法？
-
空间复杂度$S(n)$
-
时间复杂度$T(n)$：$O(\log n)\le O(n)\le O(n\log n) \le O(n^{2}) \le O(2^{n})\le O(n!)$
-
若两段算法分别有复杂度$T_1(n)=O(f_1(n))$和$T_2(n)=O(f_2(n))$，则：
-
$T_1(n)+T_2(n)=\max(O(f_1(n)),O(f_2(n)))$
-
$T_1(n)\times T_2(n)=O(f_1(n)\times f_2(n))$
-
-
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
-
if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体取三者中最大
-