算法和算法分析

算法是问题求解步骤的描述。这种描述具有五个特性。

• 有穷性 算法需要在有穷的步骤、时间内完成
• 确定性 算法的每一个步骤只有唯一的执行路径不能有歧义
• 可行性 算法中的每个操作必须是可实现的
• 输入 可以有零个或多个输入
• 输出 必须有一个或多个输出，不产出算法就没有意义

算法的设计要求：

• 正确性 正确性的级别1、程序无语法错误 2、需要有符合逻辑的输出 3、可以满足极端数据的输入 4、对一切合法输入都有满足规格说明的结果
• 可读性 易于理解与交流，便于今后修改与调试
• 健壮性 对于非法输入可以有合理的处理和反馈
• 效率与低存储量需求

算法的度量
1、事后统计
直接在计算机上运行，计算运行时间。因为不同机器上运行时间有差异，而且相同机器在不同情况下性能存在差异所以只能够粗略计算。
2、事前统计法
通过分析程序中原操作的频度（原操作的出现次数）与问题规模n所形成的函数来确定算法的渐进时间复杂度（简称时间复杂度），时间复杂度分为：

• 最好时间复杂度 输入样本为最少执行次数时的时间复杂度
• 平均时间复杂度 获取所有样本及其出现概率，将其加权后算出平均的时间复杂度
• 最坏时间复杂度 输入样本为最多执行次数时的时间复杂度
  由于平均复杂度的样本及其加权难以计算，故一般使用最坏时间复杂度。时间复杂度一般只需要取出问题规模的增长率或阶即可。

空间复杂度
除输入和程序本身外所需的辅助空间。如果所需空间为常数则称该算法原地工作。