文章目录

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

写在前面的话

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

算法性能评价

评价算法的性能主要从两个方面进行评价：时间复杂度和空间规模，记录的方式通常用大 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 + 3 n 2 + 2 n + 1 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*n^3 2∗n3 近似表示总的执行次数，记作： O ( n 3 ) O(n^3) O(n3)；
• 计算空间复杂度：上述存储空间包括，结果矩阵空间和3个循环变量，即为 S ( n ) = n 2 + 3 S(n) = n^2 + 3 S(n)=n2+3，可以认为为： O ( n 2 ) 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(1)$；

几种常见时间复杂度对比

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！