算法

算法的定义

对特定问题求解方法和步骤的一种描述，计算机中是一套指令的序列

算法的特性

  • 有穷性，会在有穷步后结束
  • 确定性，相同的输入得到相同额输出
  • 可行性，可以使用基本操作执行有限次来完成
  • 输入&输出

算法的评价标准

  • 时间线率与空间效率（存储空间），这两者有时会矛盾

事前分析法

算法中简单操作次数*每次操作所需时间

每条语句执行次数*执行一次所需时间

渐进空间复杂度

算法本身占据的空间+算法所需要的辅助空间称之为空间复杂度

为了方便比较，我们一般只比较算法运算次数的数量级，n2一定比n3好。

渐进时间复杂度

随着规模n的增大，算法执行的时间的增长率和fn的增长率相同，他们被称之为渐进时间复杂度。

例题