算法分析

算法的特性

• 有穷性 一个算法必须总是（对于任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只能有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
• 可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
• 输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
• 输出 一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

算法设计的要求

通常设计一个“好”的算法应考虑达到以下目标。

• 正确性 算法应当满足具体问题的需求。
  • a 程序不含语法错误。
  • b 程序对于几组输入数据能够得出满足规格说明要求的结果。
  • c 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。
  • d 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
    通常以第c层意义的正确性作为衡量一个程序是否合格的标准。
• 可读性 算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
• 健壮性 当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
• 效率与低存储量需求 通俗地说，效率指的是算法执行的时间。存储量需求指算法执行的过程中所需要的最大存储空间。这与问题的规模有关，而且存在一些矛盾。

算法效率的度量

事后统计的办法

很多计算机都有计时功能，有的可精确到毫秒级，但这种方式依赖于计算机的硬件、软件等环境因素，有时很容易掩盖算法本身的优劣。因此人们常常采用另一种事前估算的方法。

事前估算的方法

一个用高级语言编写的程序在计算机上运行所损耗的时间取决于下列因素。
1. 依据的算法选用何种策略；
2. 问题的规模；
3. 书写程序的语言；
4. 编译程序所产生的机器代码的质量；
5. 机器执行指令的速度；
显然，影响算法运行时间的因素有很多，当我们描述算法效率时，是否可以绕过他们呢？

时间复杂度：T(n)=O(f(n))

多数情况下，原操作是循环内最深处的操作，而算法的执行时间于该操作重复执行的次数成正比。

算法的存储空间需求

类似于算法的时间复杂度，称为空间复杂度
S(n)=O(f(n))