数据结构与算法

什么是算法？

• 数据结构与算法的关系密切，单独说其中一个，犹如唱一个独角戏，放在一起说才有意思~
• 算法的定义：

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有序序列，并且每条指令表示一个或多个操作。

算法的特性：

• 算法中至少有0个输入，至少有一个输出。

• 有穷性：算法不可以陷入死循环；算法的执行时间在可接受的范围之内。

• 确定性：

  算法的每一个步骤都具有确定的含义，不会出现二义性，算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果，每个步骤被精确定义而无歧义

• 可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成

算法设计的要求

• 正确性

  算法正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。

  正确性有四个层次：

1. 算法的程序没有错误
2. 算法程序对于合法的输入数据能够产生满足要求的输出结果
3. 算法程序对于非法的输入程序能够得出满足规格说明的结果
4. 算法程序对于精心选择的、甚至刁难的测试数据都有满足的输出结果。

• 可读性

算法设计的另一个目的是为了便于阅读、理解、交流。

• 健壮性

当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

• 时间效率高和存储量低
  也就是时间短，占用内存小。

算法效率的度量方法

• 事后统计法（不适用）
• 事前分析法
  一个高级程序设计语言编写的程序在计算机上运行时所消耗的时间取决于下列因素。
  1. 算法采用的策略，方法。
  2. 编译程序产生的代码质量
  3. 问题的输入规模
  4. 机器执行指令的速度

一般从第三点切入分析！