计算机程序设计的空间时间转换优化

第第页计算机程序设计的空间时间转换优化在计算机程序设计中，两个最重要的指标是时间复杂度和空间复杂度。时间复杂度是指程序运行时所需要的时间，简称时间。由于计算机CPU执行指令时是由CPU内部的计算器单挑指令依次执行（多核计算机除外），因此时间复杂度可以简单的由指令的执行次数来决定，简称时间；通常我们通过输入数据的规模来表示，例如程序输入的规模是n个数据，n的线性倍数的时间复杂度：执行1n次运算，或者执行2n运算可以统称为O（n），而（n-1）*n次运算，n*n次运算则可以统称为O（n2）。空间复杂度是指在程序执行时，所需要的额外的临时存储空间来存储临时的运算结果，空间复杂度的衡量可以通过类似时间复杂度衡量的规则，这里不再赘述。

【关键词】转换优化计算机程序设计

通常在设计程序时，要考虑时间和空间的平衡以追求合理的时间和空间。通过合理的数据存储以及操作，空间复杂度可以有效地降低时间复杂度。单纯的追求时间或者空间之一，则有可能造成无法接受的错误。例如如果时间复杂度过于高，则程序的时间响应速度会非常慢，当输入问题的数据量达到一定规模，程序可能会无限长的运行下去。同样，由于计算机的内存空间是有限的，当空间要求过大时，程序可能会用光所有的内存空间，这样程序会因为空间不足无法继续运行。一下我们以一个简单的实际问题来表述时间和空间的转化，以及平衡的复杂度安排的重要性。

假设我们有如下问题：输入n个整数（n>1），返回这n个数据是否有重复。

1首先我们考虑最简单不用临时存储的情况，程序数据如下：

对输入的每一个数据依次执行：

查看每一个其他的数字，对当前数据进行比较：

如果相同，则返回程序结果有重复。

如果不同，则对下一个数字进行分析。

我们对如上的设计进行分析，在最快的情况，前两个数就有重复，那么一次比较就知道有重复。在最坏的情况下，?即n个数字没有重复，对每一个数字，我们都要进行n（实际上是n-1次，我们用n来近似）次比较。所以当不用临时存储总的运算量是n*n次比较。在实际问题中，由于我们不知道问题的情况，无法预测有没有重复或者在哪里重复，所以我们要一直用最坏的情况进行分析。在此问题中时间复杂度是n*n，没有用到辅助空间。

2程序优化

此程序可以进行优化，对每个数据和其他数据比较时，不用和该数之前的数据比较，因为该次比较已经被执行过了。比如：对1，2，3，这个问题进行比较，首先我们比较1与2，1与3，然后我们开始对第二个数分析，这时不用继续比较2与1，因为1与2已经执行过，只需要比较2与3程序修改

所以修改程序如下：

对输入的每一个数据依次执行：

查看每一个在此数据之后的数字，对当前数据进行比较：

如果相同，则返回程序结果有重复。

如果不同，则对下一个数字进行分析。

我们对如上的设计进行分析，在最坏的情况下，即n个数字没有重复，对第一个数字，我们要进行n（实际上是n-1次，我们用n来近似）次比较，第二个数字n-1次比较，第三个数字n-2次比较……所以当不用临时存储总的运算量是n（n+1）/2次比较，没有用到辅助空间。

最后我们用一个带有临时存储空间的算法：我们把每一个数据存到临时空间里（注：此临时空间能提供非常快的存储和查看操作，忽略存储和查看的操作时间），查看当前数据是否已经在存储空间内，如果有，则返回是，如果没有，则继续下一个数据：

3创建一个临时的空存储空间

对输入的每一个数据依次执行：

查看存储空间是否有这个数据

如果有，则返回程序结果有重复。

如果没有，则对下一个数字进行分析，并且将当前数据储存到存储空间。

我们对如上的设计进行分析，在最坏的情况下，即n个数字没有重复，对每一个数字，我们都要进行1次查看，所以当使用临时存储总的运算量是n，额外的辅助空间大小也为n。

到此，我们的程序设计完毕，为什么利用辅助存储降低时间复杂度重要呢？我们进行如下分析：

假设有计算机A，每微秒执行一次指令，那么此计算机每秒钟可以执行106次指令。假设程序的输入为10个数，那么三个程序所需要的时间依次为T1=10*10/106=0.0001秒，T2=（10*11/2）/106=0.000055秒，T3=10/106=0.00001。在输入规模不大时候，相差不大。如果输入为10000个数，三个程序所需要的时间为T1=104*104/106=100秒，T2=（10000*10001/2）/106=0.000055=50.005秒，而T3=10000/106=0.01秒。可以计算，当输入为一百万个数字时，第一个程序需要运行27小时，而第三个程序只需要一秒钟！

我们换另外一种分析方法，如果我们有另外一条比较快的电脑B，每秒钟可以进行109运算，则B电脑比A电脑快1000倍！我们用慢电脑A处理有额外空间的程序，快电脑B处理没有额外存储的第一个程序，那么当输入为10万个整数时，A电脑需要0.1秒处理该问题，B电脑需要10秒处理该问题！A电脑在本身速度比B小1000倍的时候，计算速度反而可以可以比B快100倍。可见一个优化的算法可以迅速的提高电脑响应速度，而不需要花费太多成本在提高电脑本身的速率上面。

可以看出，当问题规模变大时，额外的辅助存储可以大规模的降低时间复杂度。有些读者可能会质疑额外的存储可能会很大，但是以这个问题为例，最差的情况下需要10000个整数的存储空间。一个整数占4B，10000个整数只需要40KB的存储空间，小于一张小图片的大小，几乎相当于一个纯文本文件的大小。由此可见适当的利用空间存储可以有效的减少额外存储。