算法分析

• 算法效率的考虑：
  1. 时间效率： 指的是算法所耗费的时间；
  2. 空间效率： 指的是算法执行过程中所耗费的存储空间
  • 时间效率和空间效率有时候是矛盾的。
• 算法时间效率的度量
  • 算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。
  • 两种度量方法
    • 事后统计
      • 将算法实现，测算其时间和空间开销。
    • 事前分析
      • 对算法所消耗资源的一种估算方法。
• 事前分析方法：
  • 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需要的时间与算法中进行的简单操作次数乘积 $$算法运行时间=一个简单操作所需的时间\times 简单操作次数$$
  • 也即算法中每条语句的执行时间之和 $$算法运行时间=\sum 每条语句频度\times 该语句执行一次所需的时间$$

每条语句执行一次所需的时间，一般是随机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的，它与算法无关。

所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。

这就可以独立于不同机器的软硬件环境来分析算法的时间性能了。

我们把算法所耗费的时间定义为该算法中每条语句的频度之和。

为了便于比较不同算法的时间效率，我们仅比较它们的数量级

[!NOTE] 时间复杂度
若有某个辅助函数 $f(n)$ ，使得当 $n$ 趋近于无穷大时， $\frac{T(n)}{f(n)}$ 的极限值为不等于零的常数，则称 $f(n)$ 是 $T(n)$ 的同数量级函数。记作 $T(n)=O(f(n))$ ，称 $O(f(n))$ 为算法的渐进时间复杂度(O是数量级符号)，简称时间复杂度。

算法中基本语句重复执行的次数是问题规模n的某个函数 $f(n)$ ，算法的时间量度记作： $T(n)=O(f(n))$
它表示随着n的增大，算法执行的时间的增长率和 $f(n)$ 的增长率相同，称渐进时间复杂度。

分析算法时间复杂度的基本方法

1. 找出语句频度最大的那条语句作为基本语句
2. 计算基本语句的频度得到问题规模 $n$ 的某个函数 $f(n)$
3. 取其数量级用符号 “O” 表示