Chinaunix首页 | 论坛 | 博客
  • 博客访问: 151790
  • 博文数量: 40
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 908
  • 用 户 组: 普通用户
  • 注册时间: 2013-09-03 11:03
个人简介

学习linux

文章分类
文章存档

2014年(7)

2013年(33)

我的朋友

分类: C/C++

2013-09-11 11:32:39

你也许和我开始学习算法的观点一样,认为学习算法没有什么用处?不过,如果你是只做C++或者Java等基本程序的设计,的确不用学习算法,
用它们本身提供的数据结构,如数组,向量,链表,再用它们的函数就ok了。但是一旦涉及大量数据的处理,就必须仔细设计数据结构和算法了。这时还用语言本身提供的,效率就很低了,因为它们是面向通用的。对于不同的数据量,为了效率最好,也要选择不同的算法,就比如排序的算法。
学习算法第一步,要会分析不同算法的效率,也就是该算法需要多少时间和空间(主要是时间)。这种分析能力还有助于知道如何设计好的算法。那么如何分析算法的运行时间呢?

1. 计算机模型:
    分析一个算法的运行时间要在一个理想计算机模型下,假设模型机每做一条基本指令都是一个时间单位1,比如加,减,乘,除。还有模型机
    的空间是无限的,即内存很大,而且从磁盘读入和写到磁盘的时间不计入(虽然这个时间很大,但是不同算法的差距不在这里)。

2. 什么时间?
    到底要分析算法的什么运行时间?运行时间有最坏情况下的运行时间和平均情况的运行时间,我们一般分析最坏情况下的运行时间,因为这是
    算法的上界而且比平均情况更好分析。运行时间一般是输入数据量N的函数,比如6N+2。

3. 如何简化计算?
    如果对最坏情况下的运行时间精确计算,是不可能的。我们的目的是比较出多个算法谁的效率更高。比如两个算法的运行时间为A(N)=6N+2,
    B(N)=N
2,可以看曲线图像,B(N)的增长率比A(N)高,从某个点之后,B(N)>A(N),所以一般舍弃常数项;若A(N)=60N+2,可以看出还是这
    个趋势,只是那个转折点后移了,所以系数也一般舍弃。当然,如果A(N)=6N+2,B(N)=7N+2,舍弃后都是N,肯定比较不了,那还是
    要计入系数,不过两个思路不同的算法一般不会是这个样子的。还有如果A(N)=N3+N2+N+1,显然N3的增长率是主要的,所以后面的低阶项
    也要舍弃。

4. 运行时间如何表达?
    从上面可以看出,我们有时会估计过高,但是这不影响体现算法整体的性能。如上面A(N)=6N+2,可以表示为A(N)=O(N),说明A(N)的运行
    时间上限可以用N的一个式子表示;A(N)=N3+N2+N+1,可以表示为A(N)=O(N3),说明A(N)的时间上限可以用N3的式子表示。可以这样
    简洁表示都是基于上面如何简化的思想。因为对于比较出两个算法性能高低的结果没有影响。

5. 一个例子:
    这个算法是计算一个序列最大子序列和的问题,比如序列-2,11,-4,13,-5,-2最大子序列和为20,即11+(-4)+13=20。

点击(此处)折叠或打开

  1. int Max(const int A[],int N)
  2. {
  3.     int ThisSum,MaxSum,i,j,k;    //声明不占用时间
  4.     MaxSum=0;                    //赋值时间单位1,舍弃
  5.     for(i=0;i
  6.         for(j=i;j
  7.         {
  8.             ThisSum=0;           //时间单位1,外面两层循环
  9.             for(k=i;k
  10.                 ThisSum+=A[k];   //时间单位1,外面三层循环
  11.             if(ThisSum>MaxSum)
  12.                 MaxSum=ThisSum;  //时间单位1,外面两层循环
  13.         }
  14.     return MaxSum;
  15. }
     我们估算最坏情况的运行时间,第一层循环N次,第二层循环N-i次,最坏时是N,第三层循环j-i+1次,最坏也是N,所以T(N)=O(N3),
    两层循环内的赋值和判断为O(N2),低阶舍弃;最终这个算法的运行时间A(N)=O(N3)。显然,效率很低。

    可以看出算法运行时间主要用在循环上,要想提高算法效率就要减少循环,实际上第三层循环是不需要的。看下面:

点击(此处)折叠或打开

  1. int Max(const int A[],int N)
  2. {
  3.     int ThisSum,MaxSum,i,j;      //声明不占用时间
  4.     MaxSum=0;                  //赋值时间单位1,舍弃
  5.     for(i=0;i<N;i++)      //循环了N次
  6.     {
  7.         ThisSum=0;     //时间单位1,外面一层循环
  8.         for(j=i;j<N;j++) //循环了N-i次
  9.         {            
  10.             ThisSum+=A[j]; //时间单位1,外面两层循环
  11.             if(ThisSum>MaxSum)
  12.                 MaxSum=ThisSum; //时间单位1,外面两层循环
  13.         }
  14.     }
  15.     return MaxSum;
  16. }
    按照相同的道理分析,这个算法的运行时间A(N)=O(N2)。

阅读(1456) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~