简单算法分析#

度量算法效率的方法：

事后分析法

先将算法实现，然后输入适当的数据运行，测量其时间和空间上的开销。

缺点： ①编写程序实现算法将花费较多的时间和精力，②所得实验结果依赖于计算机的软硬件等环境因素，有时容易掩盖算法本身的优劣。
事前分析估算——渐进复杂度

算法的时间复杂度：

撇开于计算机软硬件有关的因素，影响算法时间代价的最主要因素是问题规模。

问题规模是指输入量的多少。

基本语句是执行次数与整个算法的执行次数成正比的语言，基本语句对算法运行时间贡献最大，是算法中最重要的操作。

这种衡量效率的方法得出的不是时间量，而是一种增长趋势。换言之，只考察当问题规模充分大时，算法中的基本语句的执行次数在渐进意义下的阶，称做算法的渐进时间复杂度，简称时间复杂度，通常的用 $O$ 记号表示。

算法的空间复杂度：

算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间是除了算法本身和输入输出数据所占据空间外，算法临时开辟的存储空间。通常记作：

$S(n) = O(f(n))$

n为问题规模

算法分析举例#

例1

1
++x;

++x 是基本语句，执行次数为1，时间复杂度为 $O(1)$ ，称为常量阶

例2

1
for(int i = 0; i < n; i ++)
2
    ++x;

++x 是基本语句，执行次数是 n，时间复杂度为 $O(n)$ ，称为线性阶

例3

1
for(int i = 0; i < n; i ++)
2
  for(int j = 0; j < n; j ++)
3
        ++x;

++x 是基本语句，执行次数为 $n^2$ ，时间复杂度为 $O(n^2)$ ，称为平方阶

例4

1
for(int i = 0; i < n; i ++)
2
    for(int j = 0; j < n; j ++)
3
    {
4
        c[i][j] = 0;
5
        for(int k=1; k < n; k ++)
6
            c[i][j] += a[i][k] * b[k][j];
7
    }

c [i] [j] += a [i] [k] * b [k] [j] 是基本语句，由于是一个三重循环，所以总执行次数为 $n^3$ ，时间复杂度为 $O(n^3)$ ，称为立方阶。

例5

1
for(int i = 0; i < n; i ++)
2
    for(int j = 0; j < i; j ++)
3
        ++x;

++x 是基本语句，执行次数为： $\sum\limits_{i=1}^n \sum\limits_{j=1}^i 1 = \frac{n(n-1)}{2}$ ，所以时间复杂度为 $O(n^2)$ 。分析策略是从内部向外展开。

例6

1
for(int i = 1; i < n; i *= 2)
2
    ++x;

++x 是基本语句，设其执行次数为 $T(n)$ ，有 $2^{T(n)} \leq n$ ，即 $T(n) \leq \log_2 n$ ，所以时间复杂度为 $O(\log_2 n)$ ，称为对数阶

原文链接：CSDN