【数据结构】算法效率的度量方法

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

🎏事后统计方法

🎏事前分析估算方法

🎏函数的渐进式增长

结语

在上篇文章中我们提到了算法的设计要求中我们要尽量满足时间效率高和存储量低的需求.这里的时间效率大都指算法的执行时间.

而算法的执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量.度量一个程序的执行时间通常有两种方法:事后统计方法和事前分析估算方法.

🎏事后统计方法

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

但这种方法存在一些缺陷:

因为要依靠设计好的程序来测试,那么我们就必须依据算法事先编好程序,这通常需要花费大量的时间和精力,并且如果最后的测试结果表明这是个很糟糕的算法,那么之前的所有努力就都白费了.
时间的比较依赖于计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣.计算机的处理器,所用操作系统,编译器,运行框架等软件的不同,也可以影响它们的结果,就算是同一台机器,CPU使用率和内存占用情况不一样,也会造成细微的差异.
算法的测试数据设计困难,并且程序的运行时间往往还与测试数据的规模有很大关系,效率高的算法在小的测试数据面前往往得不到体现.

基于上面的缺陷,我们常常采用另一种事前分析估算的方法:事前分析估算方法.

🎏事前分析估算方法

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

一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:

依据的算法选用的策略,方法.
问题的规模,如求100以内还是1000以内的素数.
编译产生的代码质量.
书写程序的语言,对于同一个算法,实现语言的级别越高,执行效率就越低.
机器执行指令的速度.

这五个因素中,第一条是算法好坏的根本,第三条要由软件来支持,第四条要看程序员的选择,第五条要看硬件性能.这表明使用绝对的时间单位衡量算法的效率是不合适的.

抛开这些与计算机硬件,软件有关的因素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模.

我们拿高斯求和算法举个例子:

从1加到100,第一种算法:

int i=0;            /*执行1次*/
int sum=0;          /*执行1次*/
int n=100;          /*执行1次*/
for(i=1;i<=n;i++)   /*执行n+1次*/
{sum=sum+i;      /*执行n次*/
}
printf("%d",sum);   /*执行1次*/

第二种算法:

int i=0;            /*执行1次*/
int sum=0;          /*执行1次*/
int n=100;          /*执行1次*/
sum=(1+n)*n/2;      /*执行1次*/
printf("%d",sum);   /*执行1次*/

显然,第一种算法一共执行了1+1+1+(n+1)+n+1=2n+5次.而第二种算法一共执行了1+1+1+1+1=5次.

事实上这两种算法的前三条语句和最后一条语句是一样的,所以我们只需要关注中间那部分代码即可.我们把循环看作一个整体,忽略头尾循环判断的开销,那么这两个算法其实就是n次与1次的差距.这样一比,两种算法的好坏显而易见了.

通过这个例子我们可以看出,测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数.运行时间与这个计数成正比.

我们不关心编写程序所用的程序设计语言是什么,也不关心这些程序将跑在什么样的计算机中,我们只关心它所实现的算法.

这样,不计那些循环索引的递增和循环终止条件,变量声明,打印结果等操作,最终,在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤.

我们在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数.

如上面那个例子,同样的问题输入规模是n,第一种算法需要一段代码运行n次.那么这个问题的输入规模使得操作数量是f(n)=n.而第二种,无论n为多少,运行次数都为1,即f(n)=1.

可以看到,随着n值的越来越大,它们在时间效率上的差异也就越来越大了.

🎏函数的渐进式增长

函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n).

我们来看一个例子:算法A是n^2,

算法B是2n^2,

算法C是3n+1,

算法D是2n^2+3n+1.

次数	算法A(n^2)	算法B(2n^2)	算法C(3n+1)	算法D(2n^2+3n+1)
n=1	1	2	4	6
n=2	4	8	7	15
n=5	25	50	16	66
n=10	100	200	31	231
n=100	10,000	20,000	301	20,301
n=1,000	1,000,000	2,000,000	3,001	2,003,001
n=10,000	100,000,000	200,000,000	30,001	200,030,001
n=100,000	10,000,000,000	20,000,000,000	300,001	20,000,300,001
n=1,000,000	1,000,000,000,000	2,000,000,000,000	3,000,001	200,000,3000,001