算法分析

发表于 分类于 本文字数： 2.5k
算法的时间复杂度和空间复杂度

时间复杂度

  问题规模：问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示
  语句频度：一条语句的重复执行次数称作语句频度

  设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。
  如下算法频度之和可以记为$f(n)$，$f(n)=n+1+n^2+n+n^2+1$，该算法的执行时间与$f(n)$成正比

1
2
3
4
5
6
for (int i = 0; i < n; i++) {         // 执行频度为 n+1
    for (int j = 0; j < n; j++) {     // 执行频度为 (n+1)*n
        printf("arr = %s\n", arr[i]); // 执行频度为 n*n
    }
}
printf("over\n");                     // 执行频度为 1

  当$n \to \infty$时，$f(n)$与$n^2$同阶，或者说数量级相同，用$O$来表示这个数量级，记作$T(n) = O(f(n)) = O(n^2)$

算法的时间复杂度分析

常量阶

  如下代码，语句频度$f(n) = 2$，算法的执行时间是一个与问题规模n无关的常数，所以算法的时间复杂度$T(n) = O(1)$，称为常量阶

1
2
3
if (i < j) {           // 执行频度为1
    printf("i < j\n"); // 执行频度为1
}

线性阶

  如下代码，语句频度$f(n) = 3+3n+3+3n$，算法的时间复杂度$T(n) = O(n)$，称为线性阶

1
2
3
4
5
for (int i = 0; i < 3; i++) {     // 执行频度为 4
    for (int j = 0; j < n; j++) { // 执行频度为 (n+1)*3
        printf("j = %d\n", j);    // 执行频度为 3n
    }
}

平方阶

  如下代码，语句频度$f(n) = n+1+n^2+n+n^2$，算法的时间复杂度$T(n) = O(n^2)$，称为平方阶

1
2
3
4
5
for (int i = 0; i < n; i++) {     // 执行频度为 n+1
    for (int j = 0; j < n; j++) { // 执行频度为 (n+1)*n
        printf("j = %d\n", j);    // 执行频度为 n*n
    }
}

立方阶

  如下代码，语句频度$f(n) = n+1+n^2+n+n^3+n^2+n^3$，算法的时间复杂度$T(n) = O(n^3)$，称为立方阶

1
2
3
4
5
6
7
for (int i = 0; i < n; i++) {         // 执行频度为 n+1
    for (int j = 0; j < n; j++) {     // 执行频度为 (n+1)*n
        for (int k = 0; k < n; k++) { // 执行频度为 (n+1)*n*n
            printf("k = %d\n", k);    // 执行频度为 n^3
        }
    }
}

对数阶

  对数阶的时间复杂度计算是比较麻烦的，详细说一下
  如下代码，假设在$n$足够大的前提下，

1
2
3
for (int i = 1; i < n; i = i*2) {
    printf("i = %d\n", i);  // 执行频度为小于 log_2 n + 1 的整数
}

当循环中的printf第一次被执行时，将会输出1，然后是2 4 8 16…，第$f(n)$次执行时，$i = 2^{f(n)-1}$，由于$i \lt n$，所以$2^{f(n)-1} \lt n$，那么这一行的执行频度$f(n) \lt \log_2 n + 1$，即$f(n)$是一个小于$\log_2 n + 1$的整数，

循环轮次第1次第2次第3次第4次第5次第$f(n)$次
i的值124816$2^{f(n)-1}$

那么当$n=8$时，$\log_2 8 + 1 = 4$，printf所在行的执行频度$f(n) \lt 4$，得到$f(n) = 3$；而当$n=9$时，$\log_2 9 + 1 \gt 4$，printf所在行的执行频度$f(n) \lt \log_2 9 + 1$，得到$f(n) = 4$
  由上可知代码中的语句频度$f(n) = \log_2 n + 2 + \log_2 n + 1$，所以时间复杂度$T(n) = O(\log_2 n)$

  须知： $ $ \begin{array} {c} O(1) \lt O(\log_2 n) \lt O(n) \lt O(n\log_2n) \lt O(n^2) \lt O(n^3) \lt O(2^n) \lt O(n!) \end{array} $ $

空间复杂度

  空间复杂度作为算法所需储存空间的量度，它也是问题规模n的函数，记作$S(n) = O(f(n))$
  空间复杂度只需要分析算法在实现时所需要的辅助空间，若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为$O(1)$
  如下两种数组逆序算法，第一种算法的空间复杂度为$O(1)$，因为它只借助了一个变量t，与问题规模n大小无关；

1
2
3
4
5
for (int i = 0; i < len/2; i++) {
    int t = arr[i];
    arr[i] = arr[len - i - 1];
    arr[len - i - 1] = t;
}

第二种算法空间复杂度为$O(n)$，因为额外借助了一个与原数组等长的辅助数组

1
2
3
4
5
6
7
int temp[len];
for (int i = 0; i < len; i++) {
    temp[len - i - 1] = arr[i];
}
for (int i = 0; i < len; i++) {
    arr[i] = temp[i];
}