6_算法效率的度量

1. 常见的时间复杂度

常见的时间复杂度

2. 算法分析示例

int find(int a[], int n, int v)
{
    int ret = -1;
 
    for(int i=0; i<n; i++)
    {
        if(a[i] == v)
        {
            ret = i;
            break;
        }
    }
    
    return ret;
}

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相关

推导时间复杂度的方法同样适用于空间复杂度， 如当算法所需要的空间是常数时，空间复杂度为S(1)。

4. 空间与时间的策略

• 多数情况下，算法的时间复杂度更令人关注
• 如果有必要，可以通过增加额外空间降低时间复杂度
• 在某些必要的情况下，也可以通过增加算法的耗时降低空间复杂度

编程说明：空间换时间

/*
    问题： 
    在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。
    设计一个算法，找出出现次数最多的数字。
*/

#include <iostream>

using namespace std;

void search(int input[], int n) // O(n)  
{   
    int arr[1000] = {0};
    int max;
    
    for(int i=0; i<n; i++)
    {
        arr[input[i]-1]++;
    }
      
    for(int i=0; i<1000; i++)
    {    
        if(arr[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