算法速度影响因素的本质
表面上，算法速度的影响因素繁多，但事实上，如果我们穷根究底的话，也会在这个看似繁乱无序的世界里找出一些本质的东西。
先考虑这么一个问题：
如果b地在a地正东方，一个人要从a地去b地，那他可以有什么方法来缩短所花的时间？
第一当然是交通工具。选择汽车和步行自然不可能是相同的效果，这对应与下文的第一部分：函数存储
第二是不走弯路，若他向东南方向走了，那他就在南北方向上有了向南的偏移，之后他就必须向东北方向走来抵消刚才的偏移，这对应与下文的第三部分：计算冗余。
现在让他的行进速度和其经验相关，比如，翻过第一座山后由于有了经验，今后翻山的速度会有很大的提升，这对应于下文的第二部分：过程存储
1 函数存储
计算机能以最快速度实现的操作，我们将称之为基本操作。比如简单的加减、逻辑运算，存储器读取写入，if...then语句等等。
显然，计算机能进行的基本操作越多，算法速度就越容易提升。图灵机可进行的基本操作是很少的，一个简单的加法都要计算上很多步，因此没人会去试图造台图灵机作电脑用^_^。
对输入为有限种可能的情况，我们可以建立一个散列表，将输入直接映射到内存地址上，而存储的内容为相应输入的输出结果，这样便产生了一个运行时间几乎和一次基本操作相当的算法。这样其实就是相当于把所要计算的函数直接存储到了内存里，使计算机又多了一个基本操作。可以看出这样对算法的速度提升会是惊人的（虽然是牺牲空间得到的）。这样方法其实我们在作算术中就应用到了：小学生背乘法表是为了什么？存储一系列函数，等计算更复杂的乘法时便可以将它分解成这些函数，然后快速得到结果。相必没人作乘法是先拆成加法，再一个个加起来吧？
综上所述，当算法中出现对一个函数的频繁调用，而这个函数又是定义域有限且元素不多的，我们就可以把该函数存储到内存里，做成一个基本操作，这样就会对算法效率有质的影响。
但基本操作少了也有它的好处，这样各种操作容易各司其职，功能互不交叉，要用操作a完成的功能b肯定不能替代，比如说变量值加1操作和goto语句。这样以来，要实现某个功能时就不需在各个可行的基本操作中进行孰优孰劣选择了。所以想用函数存储优化算法是很困难的，如果有一天计算机可以自己生成算法了，它是基本上不可能掌握上面所说的这种方法的，除非依赖人工智能。它可以轻松掌握的方法或许应该是下面这个：
2 过程存储
下文中将出现的“过程”不同于一般编程语言中“过程”的概念，它是指函数的一次特定调用，包括输入值和被调用函数。调用一个过程所返回的值即该输入值经该函数计算后的结果。在一次计算的某个时刻，访问任一个变量都相当于调用了一个过程，那是向前访问过去的计算结果，而调用函数是向后将数据或控制权传给未来的函数；反过来也成立，向过去只可能出现过程调用，而向未来只可能出现函数调用。
数据结构对算法速度的影响是和电子计算机提供的两个基本操作相关的，就是内存的读/写。和他们相关的其实还有建立中间变量之类一切和存储/读取相关的操作。
建立合适的数据结构，建立合适的中间变量都有可能大幅度提高算法效率，那它们的本质是什么呢？
一个量的存储便意味着今后可随时以一个单位时间的运算速度调用计算出该量的过程，这样，如果一个过程在一次计算中出现多次，那么将其第一次运行所得结果存储从而替代后来的多次运算无疑是高效的，这正是变量存读问题的关键所在：将计算过的结果存储，之后免除了计算过程，我们暂且称之为过程存储。
显然，过程存储是不同于函数存储的。后者是算法设计时就将函数“存储”了，它是运行中“存储”的；后者是通过增加基本操作来提高速度，而前者只是避免了重复计算，并未增加基本操作。
过程存储和函数存储一样，也是适用于当算法中出现对一个函数的频繁调用，而这个函数又是定义域有限且元素不多的时候。当然，它的效率会稍低。
过程存储还有另一个优美的描述，就是跨时间的信息传递。我们不妨把存储和读取的概念从视野中完全抹掉，一个量的存储只是将其传递给了未来的一个或多个函数，而读取只是接受了过去某个过程传来的输入。这样，过程的调用概念就更广了，成为了跨时间的概念。
这样我们不难理解中间变量和数据结构对算法影响的实质了，前者充当了调用过去过程的桥梁，避免了同一过程的重复计算，而后者是前者更复杂的形式，而且与指针关系紧密，所以我们暂且只举例说明。
例:
某算法的输入中包含一字符串s，算法运行中将对s进行大量的查找工作。
如果仅靠以上信息而且不考虑空间复杂度的话，我们知道散列表是存储s的最佳选择。
S中出现的所有字符通过散列函数f映射到不同的内存地址，而内存中的数据则为相应各字母在字符串中的位置。这样要比不改变S的数据结构而每次查找都用遍历S的方法好的多。
我们来分析它和过程存储的关系：建立散列表时，若在内存地址为A（值为f（K））的项中写入了一个数组，它存储了K出现在S中的所有位置。那么，这就相当于向未来的函数提供了这样一个过程的调用：
遍历S，记录所有值等于K的元素在S中的位置并将其放入一个数组中，返回这个数组。
当然，这个调用花费的时间是很短的，而远非遍历一遍S的时间。
3 计算冗余
下面我们只考虑数值计算中的情况。
且看这一段代码：
a++
a--
恐怕天下没比这更弱智的代码了吧？可它确实是代表了一类的影响因素，也就是我们要称之为计算冗余的东西。
看这个函数：
f（x）＝5x－3x
我们可以马上写出两种计算它的算法，一个按部就班的算（算法a）而另一个直接算2x的值（算法b）。然而二者在运行时间上是有不小差异的，影响二者运行时间的因素，正是计算冗余。
对算法a，如果用一个变量Y来存储结果的话，它是先被循环加x加5次，再被循环减x减3次，中间经过了先增大后减小的过程；而对算法b，却只是个增大的过程。它可以看成是a中增大x和减小x一对操作互相抵消的结果。
显然，计算冗余是由一对效果相反的操作同时出现在算法中造成的不必要的计算。但是否算法只要出现了相反操作就意味着还可以化简呢？显然不是，比如这个函数：
g（x，y）＝1+x-y
直接计算它的算法我们可以马上写出来，计算中必然会出现相反的操作，但是它已经是最简单的形式了，我们不可能靠抵消相反操作来化简它。
这二者的区别其实在于：前者计算中的一对相反操作（增大x和减小x）所进行的次数（5次和3次）是不决定于输入变量的，是仅靠算法本身就能确定的，它是算法本身所具有的一个属性，故我们可以依据它来进行算法的化简；而对于后者，一对相反操作（加1和减1）的次数（y次和z次）是决定于算法本身的，它随着输入变量不同的值而改变，因而是不可化简的。
我们可作如下总结：
一个算法中若出现了效果相反的操作且二者的次数都不是由输入变量决定的，那这个算法可以用抵消的方法化简。
虽然是在数值计算的实例中推出来的，可这个思想并不只适用于数值计算，它应该是对任何数据类型都有效的。
4 信息利用
先看这个问题：
折半查找的高效来自何处？
显然这里不关过程存储的事，必然是其他因素的缘故。
它的高效是因为利用了输入字串的有序。从信息的角度看，我们编写算法时并非对输入信息是一无所知的，它至少包含这一点，即：字串是有序的，且该序是由小到大（或反之）的。
这就是编程者对信息的利用充分与否的问题了。设计程序前必然会掌握关于该程序的一系列信息，主要包括输入数据的相关信息和功能描述。功能描述决定了程序的功能（或者说它所实现的函数），而数据相关信息则是预先知道的程序输入（函数定义域）信息的特征的描述。如果能将这些信息充分在算法中表达出来，也就是算法如果能充分利用这些信息，能对速度提升有很大影响。
类似的例子在实际应用中是很常见的，比如统计关键词被搜索的频率来调整算法，优先搜索频率高者。
本文地址：http://com.8s8s.com/it/it23252.htm