线性加速定理

在计算复杂性理论中，线性加速定理指时间复杂性可以任意地线性加速，即如果一个函数有时间的算法，则对任意小常数，必然存在时间的算法来计算；即对时间复杂性类的带数目的减少。空间复杂性也可以类似任意地线性加速。

线性加速定理简介

图灵机的线性加速定理是指：给定任意实数 c > 0 ，如果有任意图灵机在 f(n) 时间内可以解决一个问题 L 则一定存在另一个图灵机可以在 cf(n) + n + 2 的时间内解决这个问题 L。线性加速定理主要通过程序进行并行计算来实现和对问题进行算法优化。

这里提供一个对于 c = 1/2 时的简要的证明思路。假设一个包含有 k 条带和 s 个状态的图灵机 M 可以在 f(n) 的时间内解决这个问题，构造一个新的图灵机 M' 包含 k3 条带，每一个符号表示一个 M 中连续的三个符号的一个区块，即 M' 的带上的符号是 M 上的符号的压缩表示—— M' 的第 i 格上的符号表示 M 的第 2i-1 格、第 2i 格和第 2i+1 格的一个区块上的符号（注意：这些区块之间是交叠的）。在一个计算步骤中，M' 模拟 M 的计算步骤直到 M 的读写头离开 M' 当前读写头所表示的对应区块到左侧或右侧的下一格（这一模拟可以在一步中完成，因为 M 在不离开 M' 中对应区块或重复一个状态的情况下最多有 3sk3 种状态）。在这一模拟过程中， M 有可能接受（解决此问题），对应的 M' 也会接受（解决此问题）；或者 M 会一直循环下去，对应的 M' 会什么也不做（或也对应的一直循环下去）。

最后一点需要注意的地方是：由于区块可以交叠，因此这些区块可能会在交叠出包含不连续的字符。在这种情况下，最接近当前读写头位置的区块才是正确的。当发生从一个区块到另一个区块的转换时，图灵机的状态被用来暂时记录开始区块的那些交叠的符号，直到其可以被复制到目的区块的对应位置。

这一构造需要 M' 的每一步计算要对应 M 的至少两步计算。因此 M' 在最初的花费线性步骤的将输入带转换为压缩表示的步骤之后，最多还需要不会超过 f(n)/2 步。

这一证明可以被很容易的推广到所有的 c > 0 的情况，通过让每个区块使用更多相邻的符号来实现。一种叫做“带压缩定理”的相似技术可以用来在图灵机所需的空间上去掉常因数。

线性加速定理计算复杂性理论

计算复杂性理论是计算机科学理论的一个重要组成部分，当代几乎所有重要的科学问题都与计算复杂性有关，如人工智能问题，认识极限问题等，这些问题都是科学前沿的一些重要但未解决的问题。用数学方法研究各类问题的计算复杂性的学科。它研究各种可计算问题在计算过程中资源(如时间、空间等)的耗费情况，以及在不同计算模型下，使用不同类型资源和不同数量的资源时，各类问题复杂性的本质特性和相互关系。

它对计算中所需的各种资源(计算时间、存储空间等)的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。在计算一类问题时，资源耗费的多少与被计算问题本身的大小有关，它是问题大小的函数，称为问题对该资源需求的复杂度。计算复杂性理论研究的主要内容包括对复杂度函数增长的阶进行分析，探讨它们对于不同的计算模型在一定意义下的无关性，根据复杂度的阶对被计算问题分类，研究各种不同资源耗费之间的关系，对一些基本问题的资源耗费情况的上、下界作估计等。

线性加速定理方法

并行计算或称平行计算是相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。为利用并行计算，通常计算问题表现为以下特征：

（1）将工作分离成离散部分，有助于同时解决；

（2）随时并及时地执行多个程序指令；

（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。

算法优化是指对算法的有关性能进行优化，如时间复杂度、空间复杂度、正确性、健壮性。大数据时代到来，算法要处理数据的数量级也越来越大以及处理问题的场景千变万化。为了增强算法的处理问题的能力，对算法进行优化是必不可少的。算法优化一般是对算法结构和收敛性进行优化，算法结构优化简单来说对需要处理的问题，设计新的算法。算法优化目的是为了在尽可能的小的时间和空间代价下寻找问题的最优解。

线性加速定理空间复杂度与时间复杂度

空间复杂度

空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。

相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 T(n) ，定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类，举例来说，有着 T(n) = O(n) 的算法被称作“线性时间算法”；而 T(n) = O(Mn) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被称作“指数时间算法”。