第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 a[] = {1,2,3,4,5};

//最好的情况： int min = find(a,5,1); 执行一次循环，O(1)
//最坏的情况： int max = find(a,5,5); 执行5次循环，O(5)

算法的最好与最坏情况
意义：
当算法在最坏情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都满足需求。
注意：在数据结构课程中，在没有特殊说明时，所分析算法的时间复杂度都是指最坏时间复杂度。

算法的空间复杂度（Space Complexity）
-定义：S(n) = S(f(n))
　　.n 为算法的问题规模
　　.f(n)为空间使用函数，与n相关
推导时间复杂度的方法同样适用于空间复杂度
例如：
当算法所需要的空间是常数时，空间复杂度为S(1)

空间与时间的策略
-多数情况下，算法的时间复杂度更令人关注
-如果有必要，可以通过增加额外空间降低时间复杂度 （因为计算机硬件的发展速度，远远大于软件的速度）
-同理，也可以通过增加算法的耗时降低空间复杂度

#include <iostream>

using namespace std;

//注意一个数组中出现次数最多的数字，不一定只有一个。
void search(int a[],int len)
{
    int sp[1000] = {0};
    int max = 0;

    for(int i =0;i<len; i++)
    {
        sp[a[i]-1]++;

    }

    for(int i=0; i<1000; i++)
    {
        if(max < sp[i])
        {
            max = sp[i];
        }

    }

    for(int i=0; i<1000; i++)
    {
        if(max == sp[i])
            cout << i+1 <<endl;
    }

}

int main(int argc, char *argv[])
{
    int a[] = {1,1,3,4,5,6,6,6,3,3};

    search(a, sizeof(a)/sizeof(*a));

    return 0;
}