1_绪论

基本概念

• 线性结构：有且仅有一个开始和终端结点，且所有结点都最多只有一个直接前驱和一个直接后序
• 非线性结构：多个直接前驱或多个直接后继

存储结构是逻辑关系的映象与元素本身的映象

逻辑结构是数据结构的抽象，存储结构是数据结构的实现。两者综合起来建立了数据元素之间的结构关系

注意区别逻辑结构和具体数据结构 P3X3

算法评估

• 算法必须是有穷的，程序可以是无穷的
• 可行性是指算法中描述的操作可以通过已经实现的基本运算有限次来实现
• 算法有零个或多个输入，一个或多个输出
• 健壮性是指能对输入的非法数据做出反应或处理，而不会产生莫名其妙的输出结果

$O(1)<O( \log_{2}{n})<O(n)<O(n \log_{2}{n})<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})$

“常对幂指阶”

空间复杂度

1. 无论问题规模怎么改变，算法运行所需要的内存空间都是固定常量，S(n)=O(1)

   函数递归调用的空间复杂度=递归调用的深度

2. 内存空间和问题规模有关

   函数递归调用的空间复杂度$ \ne$递归调用的深度