算法效率

计算机术语

算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。

简介

定义

算法效率是指算法执行的时间，算法执行时间需通过依据该算法

度量方法

度量一个程序的执行时间通常有两种方法：（一）事后统计的方法（二）事前分析估算的方法。

事后统计的方法不利于较大范围内的算法比较（异地，异时，异境）。

事前分析估算的方法与许多因素有关，包括算法本身选用的策略、问题的规模、书写程序的语言、编译产生的机器代码质量和机器执行指令的速度等。为便于比较算法本身的优劣，应排除其它影响算法效率的因素。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量。（原操作在所有该问题的算法中都相同）

度量一个程序运行时间的方式通过时间复杂度和空间复杂度来表征。

上式表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

上式表示空间复杂度。空间复杂度可以作为算法所需存储空间的量度。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。原地工作意思是一个算法需要少量的辅助空间，且其大小不随问题规模的大小而改变。如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。

算法的最优、最差和平均效率

最差效率：指当输入规模为n时，算法的最坏情况下的效率。

最优效率：指当输入规模为n时，算法在最优情况下的效率。

平均效率：指当输入规模为n时，算法的平均效率。

大量实践经验告诉我们，我们评价一个算法是应该重点考虑最差效率这一点。

提高算法效率的方法

对数据的逻辑结构进行选择，是构造数学模型一大关键，而算法又是用来解决数学模型的。要使算法效率高，首先必须选好数据的逻辑结构。选择逻辑结构的目的是提高信息的利用效果。在解决问题的过程中，选择合理的逻辑结构是相当重要的环节。

选择合理的存储结构

数据的存储结构，分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。因为两种存储结构的不同，导致这两种存储结构在具体使用时也分别存在着优点和缺点。这里有一个较简单的例子：我们需要记录一个n×n的矩阵，矩阵中包含的非0元素为m个。此时，我们若采用顺序存储结构，就会使用一个n×n的二维数组，将所有数据元素全部记录下来；若采用链式存储结构，则需要使用一个包含m个结点的链表，记录所有非0的m个数据元素。由这样两种不同的记录方式，我们可以通过对数据的不同操作来分析它们的优点和缺点。

1．随机访问矩阵中任意元素。由于顺序结构在物理位置上是相邻的，所以可以很容易地获得任意元素的存储地址，其复杂度为O(1)；对于链式结构，由于不具备物理位置相邻的特点，所以首先必须对整个链表进行一次遍历，寻找需进行访问的元素的存储地址，其复杂度为O(m)。此时使用顺序结构显然效率更高。

2．对所有数据进行遍历。两种存储结构对于这种操作的复杂度是显而易见的，顺序结构的复杂度为O(n2)，链式结构为O(m)。由于在一般情况下m要远小于n2，所以此时链式结构的效率要高上许多。除上述两种操作外，对于其它的操作，这两种结构都不存在很明显的优点和缺点，如对链表进行删除或插入操作，在顺序结构中可表示为改变相应位置的数据元素。既然两种存储结构对于不同的操作，其效率存在较大的差异，那么我们在确定存储结构时，必须仔细分析算法中操作的需要，合理地选择一种能够“扬长避短”的存储结构。

存储结构的选择包括以下两种。

一、合理采用顺序存储结构。我们在平常做题时，大多都是使用顺序存储结构对数据进行存储。究其原因，一方面是出于顺序结构操作方便的考虑，另一方面是在程序实现的过程中，使用顺序结构相对于链式结构更便于对程序进行调试和查找错误。因此，大多数人习惯上认为，能够使用顺序结构进行存储的问题，最“好”采用顺序存储结构。其实，这个所谓的“好”只是一个相对的标准，是建立在以下两个前提条件之下的：

1．链式结构存储的结点与顺序结构存储的结点数目相差不大。这种情况下，由于存储的结点数目比较接近，使用链式结构完全不能体现出记录结点少的优点，并且可能会由于指针操作较慢而降低算法的效率。更有甚者，由于指针自身占用的空间较大，且结点数目较多，因而算法对空间的要求可能根本无法得到满足。

2．并非算法效率的瓶颈所在。由于不是算法最费时间的地方，这里是否进行改进，显然是不会对整个算法构成太大影响的，若使用链式结构反而会显得操作过于繁琐。

二、必要时采用链式存储结构。

由于链式结构中指针操作确实较繁琐，并且速度也较慢，调试也不方便，因而大家一般都不太愿意用链式的存储结构。但是，这只是一般的观点，当链式结构确实对算法有很大改进时，我们还是不得不进行考虑的。

然而，如果我们采用的是链式存储结构，那么我们需要多少数据，就只会遍历多少数据，这样不仅充分发挥了链式存储结构的优点，而且由于不需单独对某一个数据进行提取，每次都是对所有数据进行判断，从而避免了链式结构的最大缺点。我们使用链式存储结构，虽然没有降低问题的时间复杂度(链式存储结构在最坏情况下的存储量与顺序存储结构的存储量几乎相同)，但由于体现了前文所述选择存储结构时扬长避短的原则，因而算法的效率也大为提高。我们选择链式的存储结构，虽然操作上可能稍复杂一些，但由于改进了算法的瓶颈，算法的效率自然也今非昔比。由此可见，必要时选择链式结构这一方法，其效果是不容忽视的。

使用直接初始化

与直接初始化对应的是复制初始化，什么是直接初始化？什么又是复制初始化？举个简单的例子，

那么直接初始化与复制初始化又有什么不同呢？直接初始化是直接以一个对象来构造另一个对象，如用ct1来构造ct2，复制初始化是先构造一个对象，再把另一个对象值复制给这个对象，如先构造一个对象ct3，再把ct1中的成员变量的值复制给ct3，从这里，可以看出直接初始化的效率更高一点，而且使用直接初始化还是一个好处，就是对于不能进行复制操作的对象，如流对象，是不能使用赋值初始化的，只能进行直接初始化。可能我说得不太清楚，那么下面就引用一下经典吧！

以下是Primer是的原话：

“当用于类类型对象时，初始化的复制形式和直接形式有所不同：直接初始化直接调用与实参匹配的构造函数，复制初始化总是调用复制构造函数。复制初始化首先使用指定构造函数创建一个临时对象，然后用复制构造函数将那个临时对象复制到正在创建的对象”，还有一段这样说，“通常直接初始化和复制初始化仅在低级别优化上存在差异，然而，对于不支持复制的类型，或者使用非explicit构造函数的时候，它们有本质区别：

尽量减少值传递，多用引用来传递参数。

如果参数是int等语言自定义的类型可能能性能的影响还不是很大，但是如果参数是一个类的对象，那么其效率问题就不言而喻了。例如一个判断两个字符串是否相等的函数，其声明如下：

其中若使用第一个函数（值传递），则在参数传递和函数返回时，需要调用string的构造函数和析构函数两次（即共多调用了四个函数），而其他的三个函数（指针传递和引用传递）则不需要调用这四个函数。因为指针和引用都不会创建新的对象。如果一个构造一个对象和析构一个对象的开销是庞大的，这就是会效率造成一定的影响。

然而在很多人的眼中，指针是一个恶梦，使用指针就意味着错误，那么就使用引用吧！它与使用普通值传递一样方便直观，同时具有指针传递的高效和能力。因为引用是一个变量的别名，对其操作等同于对实际对象操作，所以当你确定在你的函数是不会或不需要变量参数的值时，就大胆地在声明的前面加上一个const吧，就如最后的一个函数声明一样。

同时加上一个const还有一个好处，就是可以对常量进行引用，若不加上const修饰符，引用是不能引用常量的。

减少除法运算的使用

无论是整数还是浮点数运算，除法都是一件运算速度很慢的指令，在计算机中实现除法是比较复杂的。所以要减少除法运算的次数，下面介绍一些简单方法来提高效率：

1、通过数学的方法，把除法变为乘法运算，如if(a > b/c),如果a、b、c都是正数，则可写成if(a*c > b)

2、让编译器有优化的余地，如里你要做的运算是int型的n/8的话，写成（unsigned）n/8有利于编译器的优化。而要让编译器有优化的余地，则除数必须为常数，而这也可以用const修饰一个变量来达到目的。

避免使用多重继承

在C++中，支持多继承，即一个子类可以有多个父类。书上都会告诉我们，多重继承的复杂性和使用的困难，并告诫我们不要轻易使用多重继承。其实多重继承并不仅仅使程序和代码变得更加复杂，还会影响程序的运行效率。

这是因为在C++中每个对象都有一个this指针指向对象本身，而C++中类对成员变量的使用是通过this的地址加偏移量来计算的，而在多重继承的情况下，这个计算会变量更加复杂，从而降低程序的运行效率。而为了解决二义性，而使用虚基类的多重继承对效率的影响更为严重，因为其继承关系更加复杂和成员变量所属的父类关系更加复杂。

将小粒度函数声明为内联函数

调用函数是需要保护现场，为局部变量分配内存，函数结束后还要恢复现场等开销，而内联函数则是把它的代码直接写到调用函数处，所以不需要这些开销，但会使程序的源代码长度变大。

所以若是小粒度的函数，如下面的Max函数，由于不需要调用普通函数的开销，所以可以提高程序的效率。

全国各地天气预报查询

上海市

云南省

云南省

云南省