qiuyadong's Homepage

时间复杂度和空间复杂度

2019-02-20

算法效率的度量方法

1.事后统计方法

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

2.事前分析估算方法

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

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

算法采用的策略,方案 编译产生的代码质量 问题的输入规模 机器执行指令的速度

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

实现:1+2+…+99+100

//第一种算法:
int i, sum = 0, n = 100;   // 执行1次
for( i=1; i <= n; i++ )    // 执行了n+1次
{
    sum = sum + i;          // 执行n次
}

//第二种算法:

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

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

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

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

分析一个算法的运行时间时,重要的是把基本操作的数量和输入模式关联起来。



Comments