6_算法效率的度量

1. 常见的时间复杂度
6_算法效率的度量
文章图片
常见的时间复杂度
6_算法效率的度量
文章图片
2. 算法分析示例

int find(int a[], int n, int v) { int ret = -1; for(int i=0; i

int arr[5] = {1, 2, 3, 4, 5}; int min = find(arr, 5, 1); //最好的情况,执行1次循环, O(1)int max = find(arr, 5, 5); //最坏的情况,执行n次循环, O(n)

算法的最好情况与最坏情况:当算法在最坏情况下仍能满足需求时,可以推断,算法的最好情况和平均情况都满足需求。
note:课程中在没有特殊情况说明时,所分析的算法时间复杂度都是指最坏时间复杂度
3. 算法的空间复杂度(Space Complexity)
定义:算法从运行到结束所占内存空间的大小。
S(n) = S(f(n)) n 为算法的问题规模 f(n) 为空间使用函数,与n相关

【6_算法效率的度量】推导时间复杂度的方法同样适用于空间复杂度, 如当算法所需要的空间是常数时,空间复杂度为S(1)。

6_算法效率的度量
文章图片

4. 空间与时间的策略
  • 多数情况下,算法的时间复杂度更令人关注
  • 如果有必要,可以通过增加额外空间降低时间复杂度
  • 在某些必要的情况下,也可以通过增加算法的耗时降低空间复杂度
编程说明:空间换时间
/* 问题: 在一个由自然数1-1000中某些数字所组成的数组中,每个数字可能出现零次或者多次。 设计一个算法,找出出现次数最多的数字。 */#include using namespace std; void search(int input[], int n) // O(n) { int arr[1000] = {0}; int max; for(int i=0; i max) { max = arr[i]; } }for(int i=0; i<1000; i++) { if( arr[i] == max ) { cout << i + 1 << endl; } } }int main() { int input[10] = {999, 1000, 1000, 999, 999, 1000, 2, 3, 4, 5}; search(input, sizeof(input) / sizeof(input[0])); return 0; }

输出结果:
999 1000

5. 面试题:当两个算法的大O表示法相同时,是否意味着两个算法的效率完全相同?
当算法的大O表示法相同时,意味着这两个算法的效率是在同一个级别的,但不意味着这两个算法效率完全相同。
6. 小结
  • 一般而言,工程中使用的算法,时间复杂度不超过O(n^3)
  • 算法分析与设计时,重点考虑最坏情况下的时间复杂度
  • 数据结构课程中重点关注算法的时间复杂度
  • 大O表示法同样适用于算法的空间复杂度
  • 空间换时间是工程开发中常用的策略
声明:此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记,文章中包含狄泰软件资料内容,一切版权归狄泰软件所有!
实验环境:ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4

    推荐阅读