A1算法性能评价

2021-07-15 05:19:50

文章目录

写在前面的话
算法性能评价
几种常见时间复杂度对比

写在前面的话

文档没有任何商业因素，本着共享的精神进行分享，如有素材侵权，请给我留言;
文档都是自己平时看书或工作中的笔记，观点错误的地方欢迎留言；

算法性能评价

评价算法的性能主要从两个方面进行评价：时间复杂度和空间规模，记录的方式通常用大 O 标记法；

时间复杂度：指算法在最糟糕情况下的操作数量（一条语句作为一个操作单位），间接反应算法的运行时间；
空间规模：算法执行过程中所需要的最大空间需求；算法执行期间所需要的存储空间一般包含：
- 输入数据所占的空间；如果输入数据规模与问题相关，则不计入空间规模计算；
- 程序本身所占的空间；代码空间对不同算法来说一般相差不大，和算法无关；
- 辅助变量所占的空间；

举个例子来求解时间复杂度和空间规模：

例子1：求解 n 阶矩阵相乘的结果

// 计算 n 阶级矩阵的乘积：算法语句
for(int i = 0; i < n; i++) {    // 执行 n+1 次
    for(int j = 0; j < n ; j++) {    // 执行 n*(n+1) 次
        c[i][j] = 0;    // 执行 n^2 次
        for(int k = 0; k < n; k++)    // 执行 n^2(n+1)次
            c[i][j] = a[i][k]*b[k][j];    // 执行 n^3 次
    }    
}

计算时间复杂度：
- 计算总的执行次数： $T(n) = n+1 + n*(n+1) + n^2 + n^2*(n+1) + n^3 = 2*n^3 + 3n^2 + 2n + 1$ T(n)=n+1+n∗(n+1)+n2+n2∗(n+1)+n3=2∗n3+3n2+2n+1；
- 我们可以用 $2*n^3$ 2∗n3 近似表示总的执行次数，记作： $O(n^3)$ O(n3)；
计算空间复杂度：上述存储空间包括，结果矩阵空间和3个循环变量，即为 $S(n) = n^2 + 3$ S(n)=n2+3，可以认为为： $O(n^2)$ O(n2)；

例子2：求 n 项数据之和

scanf(" %d", &n);
for(s = 0, i = 1; i <= n; i++)    // 执行 n+2次 
    s = s+i;    // 执行 n+1 次 
printf(" %d", s);

时间复杂度：可以看出操作数与规模 n 成线性关系，极为： $O(n)$ O(n)；
空间复杂度：空间消耗只有两个变量，与空间规模无关，可以记作： $O(1)$ O(1)；

几种常见时间复杂度对比

$O(log n)$ O(logn)，也叫对数时间，这样的算法包括二分查找。
$O(n)$ O(n)，也叫线性时间，这样的算法包括简单查找。
$O(n * log n)$ O(n∗logn)，快速排序的运行时间——一种速度较快的排序算法。
$O(n^2)$ O(n2)，选择排序的运行时间——一种速度较慢的排序算法。
$O(n!)$ O(n!)，旅行商问题的运行时间——一种非常慢的算法