当前位置:鱼C工作室 >数据结构和算法 > 查看文章

时间复杂度和空间复杂度1 – 数据结构和算法03

时间复杂度和空间复杂度1

 

让编程改变世界

Change the world by program


 

算法效率的度量方法

 

上一讲中我们提到设计算法要尽量的提高效率,这里效率高一般指的是算法的执行时间。

那么我们如何来度量一个算法的执行时间呢?

 

所谓“是骡子是马拉出来遛遛”,比较容易想到的方法就是我们把算法跑若干次,然后拿个“计时器”在旁边计时。

这种事后统计方法看上去的确不错,并且也并非真的要你拿个计算器在那里计算,因为计算机都有计时功能。

 

事后统计方法:这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低。

 

但这种方法显然是有很大缺陷的:

  1. 必须依据算法事先编制好测试程序,通常需要花费大量时间和精力,完了发觉测试的是糟糕的算法,那不是功亏一篑?赔了娘子又折兵?
  2. 不同测试环境差别不是一般的大!

 

我们把刚刚的估算方法称为事后诸葛亮。

我们的计算机前辈们也不一定知道诸葛亮是谁,为了对算法的评判更为科学和便捷,他们研究出事前分析估算的方法。

 

事前分析估算方法:在计算机程序编写前,依据统计方法对算法进行估算。

 

经过总结,我们发现一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:

1. 算法采用的策略,方案

2. 编译产生的代码质量

3. 问题的输入规模

4. 机器执行指令的速度

 

由此可见,抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间依赖于算法的好坏和问题的输入规模。(所谓的问题输入规模是指输入量的多少)

 

我们搬回搞死先生的那个算法来跟大家谈谈:

第一种算法:

int i, sum = 0, n = 100;   // 执行1次
for( i=1; i <= n; i++ )    // 执行了n+1次
{
    sum = sum + i;         // 执行n次
}

 

第二种算法:

int sum = 0, n = 100;     // 执行1次
sum = (1+n)*n/2;          // 执行1次

 

第一种算法执行了1+(n+1)+n=2n+2次。

第二种算法,是1+1=2次

 

如果我们把循环看做一个整体,忽略头尾判断的开销,那么这两个算法其实就是n和1的差距。

有些喜欢跟真理死磕的朋友可能对小甲鱼这观点意见不是一般的大!

因为循环判断在算法1里边执行了n+1次,看起来是个不小的数量,凭什么说忽略就能忽略?

 

淡定,请接着继续看延伸的例子:

int i, j, x=0, sum=0, n=100;
for( i=1; i <= n; i++ )
{
    for( j=1; j <= n; j++ )
    {
        x++;
        sum = sum + x;
    }
}

 

分页阅读: 1 2 3 4 下一页
为您推荐

报歉!评论已关闭.