算法分析

时间代价: 算法执行时所花费的CPU时间量
空间代价: 算法执行时所占用的存储空间量

时间代价分析

1. 事后统计：需编写程序实现算法结果，依赖于计算机软硬件环境的影响（计算机处理速度的快慢、程序设计语言执行效率的高低、以及编译程序生成目标代码的质量）
2. 事先分析估算：算法的执行时间只依赖于问题规模

算法执行所耗费的时间T是问题规模n的函数，记作T(n)：
T(n) = 基本操作(i)执行的次数 × 基本操作(i)的执行时间

在基本操作执行时间一定的情况下，算法的执行时间就只依赖于基本操作执行的次数。

在考察时间性能时，我们其实是要分析随着问题规模n的增加，基本操作执行的次数增加得快不快，也就是其增长率如何。

采用算法的渐进时间复杂度作为算法时间效率的度量，简称时间复杂度，用大O记号表示：

若存在两个正的常数 和 ，对于任意 ，都有T(n) ≤ c × 𝑓(𝑛) ，则称T(n) = O(f(n))。

定义说明了函数T(n)和f(n)具有相同的增长趋势。在求解时间复杂度时也就只用求出f(n)的增长率即可，在此意义下，基本操作就是循环最内层的原操作。

举例

1.一条简单语句的时间复杂度是O(1)。

int count = 0;

2.一个循环的时间复杂度是O(n)。

int n = 8, count = 0;
for (int i = 1; i <= n; i++)
  count++; //循环体执行n次

3.以下二重循环的时间复杂度为O()。

for (int i = 1; i <= n; i++) 
  for (int j = 1; j <= n; j++)
  count++; //循环体执行n^2次

4.以下循环语句的时间复杂度是O()。

for (int i = 1; i <= n; i *= 2) //i按2的幂（1, 2, 4,  8）递增
  count++; //循环体执行1+log2n次

5.以下二重循环的时间复杂度是O()。

for (int i = 1; i <= n; i *= 2) //循环log2n次
  for (int j = 1; j <= n; j++) //循环n次
    count++;

6.以下二重循环的时间复杂度是O(n)。

for (int i = 1; i <= n; i *= 2) //循环log2n次
  for (int j = 1; j <= i; j++) //循环i次
    count++;

循环次数：

常见数量阶：

• 一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。
• 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。
• 其余常用的算法时间复杂度还有平方阶O()、立方阶O()、对数阶O()、指数阶O()等。

各种不同算法时间复杂度的比较关系如下：
O(1) < O() < O(n) < O() < O() < O() < O() < O(n!)

空间代价分析

算法的空间代价是指算法执行时所占用的存储空间量，包括：输入数据占用的存储空间、程序指令占用的存储空间、辅助变量占用的存储空间。

辅助变量占用的存储空间是度量算法空间代价的依据。

算法在执行过程中所需要的辅助空间数量称为算法的空间复杂度S(n)，S(n)也应该是问题规模的函数，记作：
S(n) = O(f(n))
表示算法的空间增长率与f(n)的增长率相同。