绪论

数据结构

逻辑结构

四大结构

• 集合结构：其中元素除了同属于同一个集合，没有其他关系

• 线性结构：数据结构是一对一的关系

• 树形结构：元素之间存在一种一对多的关系

• 图形结构：元素是多对多的关系

物理结构

数据在存储器中的结构

• 顺序存储结构：把数据元素存储在地址连续的存储单元里
• 链式存储结构：把数据元素放在任意的存储单元里，需要一个指针存放元素的地址

算法

算法与数据结构紧密相连

算法的五个特征：

• 输入：具有零个或多个输入
• 输出：算法至少有一个输出（打印或返回）
• 有穷性：算法在执行有限的步骤之后，结束而不会无限循环，并且每一个步骤在可以接受的时间内完成
• 确定性：每一个步骤都有确定的含义，没有二义性；一定条件下的执行路径唯一；每个步骤定义精确
• 可行性：每一步都可以实现

算法设计的要求

• 正确性：就算对
  • 没有语法错误
  • 对于合法输入能产生满足要求的输出
  • 对于非法输入能产生满足规格的说明
  • 对于故意刁难的测试输入都有满足要求的输出结果？
• 可读性：便于阅读理解交流
• 健壮性：输入数据不合法也能做出相关处理，不会崩溃
• 时间效率高和储存量低

复杂度

效率与什么有关

算法的效率往往取决于：

• 算法采用的策略、方案
• 编译产生的代码质量
• 问题的输入规模
• 机器执行指令的速度

抛开环境，效率与算法优劣和输入规模有关

效率的计算方法

事后统计方法：实际运行测量时间

环境不同，浪费时间

事前估算方法

函数的渐进增长

给定两个函数$f(n)$和$g(n)$，如果存在一个整数$N$，使得对于所有的$n>N$，$f(n)$总是比$g(n)$大，我们说$f(n)$的增长渐进快于$g(n)$。

时间复杂度

大O表示法：渐进时间复杂度

用常数1取代运行时间中所有的加法常数

值保留最高项

去掉最高阶的常数

空间复杂度