一、算法简介

对特定问题的求解方法和步骤的描述

特性

算法有五大特性

• 有穷性
  • 步骤与执行时间必须是有穷的
• 确定性
  • 每一条指令必须有确切的含义，没有二义性
• 可行性
  • 算法必须是可行的。
• 输入
  • 一个算法必须要有0 or N个输入

• 输出

  • 必须要有一个或者多个输出

    算法设计要求

• 正确性

• 可读性
• 健壮性
  • 输入非法数据，算法给出对应的响应

• 高效性

  • 时间尽量少，存储要求低

    二、算法优劣分析

    一个好算法必须具备健壮性、可读性、正确性，有了上面之后，我们就需要去考虑算法的的效率;
    算法的效率主要以一下两方面考虑

• 时间效率

  • 算法当中耗费的时间
• 空间效率
  • 存储空间耗费

    时间效率和空间效率有时候是矛盾的。

算法时间效率的度量

算法时间效率依据程序在计算机耗费的时间来度量。

• 事后统计
  • 算法实现，测算时间和空间开销
• 事前分析
  • 对算法消耗的资源估算
  • 算法时间=一个操作所需要的时间X简单操作次数。

算法重复执行次数最多的就是

• 如何去求渐进时间复杂度?
  • 只考虑基本操作的执行次数..
  • 只取最高项
  1. 找出频度最大的基本语句
  2. 计算基本语句频度找出问题规模
  3. 取出数量级用O表示

时间复杂度由嵌套最深的语句频度决定

• 算法时间复杂度
  • 最坏时间复杂度
  • 平均时间复杂度
  • 最好时间复杂度

• 算法时间效率比较

  
  

算法的空间效率

渐进空间复杂度

算法要占用的空间:输入输出、指令常熟、 算法需要的使辅助空间