EITC/IS/CCTF 计算复杂性理论基础

因为运行算法所需的资源量随输入的大小而变化，所以复杂度通常表示为函数 f(n)，其中 n 是输入大小，f(n) 是最坏情况复杂度（所有大小为 n 的输入所需的最大资源量）或平均案例复杂度（大小为 n 的所有输入的资源量的平均值）。 在大小为 n 的输入上所需的基本操作的数量通常表示为时间复杂度，其中基本操作被认为在特定计算机上花费恒定的时间，并且当在不同的机器上运行时仅以恒定因子变化。 算法对大小为 n 的输入所需的内存量称为空间复杂度。

时间是最常被考虑的资源。 当术语“复杂性”不带限定词使用时，通常是指时间的复杂性。

传统的时间单位（秒、分钟等）在复杂性理论中没有采用，因为它们过于依赖所选的计算机和技术的进步。 例如，今天的计算机可以比 1960 年代的计算机更快地执行算法，然而，这是由于计算机硬件的技术突破，而不是算法的固有质量。 复杂性理论的目标是量化算法的内在时间需求，或算法对任何计算机施加的基本时间限制。 这是通过计算在计算过程中执行了多少基本操作来完成的。 这些过程通常被称为步骤，因为它们被认为在特定机器上花费恒定的时间（即，它们不受输入量的影响）。

另一个关键资源是执行算法所需的计算机内存量。

另一个经常使用的资源是算术运算的数量。 在这种情况下，使用术语“算术复杂性”。 如果计算期间出现的数字的二进制表示大小的上限已知，则时间复杂度通常是算术复杂度乘以常数因子的乘积。

计算过程中使用的整数的大小不受许多方法的限制，假设算术运算需要固定的时间是不现实的。 因此，时间复杂度（也称为位复杂度）可能会明显高于算术复杂度。 例如，对于标准技术（高斯消元法），计算 nn 个整数矩阵的行列式的算术难度是 O(n^3)。 由于在计算过程中系数的大小可能会呈指数增长，因此相同方法的位复杂度是 n 的指数。 如果将这些技术与多模运算结合使用，则位复杂度可以降低到 O(n^4)。

位复杂度在形式上是指运行算法所需的位操作数。 在大多数计算范例中，它等于时间复杂度直到一个常数因子。 计算机所需的机器字操作数与位复杂度成正比。 对于现实的计算模型，时间复杂度和比特复杂度因此是相同的。

在排序和搜索中经常考虑的资源是条目比较的数量。 如果数据排列得当，这是时间复杂度的一个很好的指标。

在所有潜在输入上，计算算法中的步骤数是不可能的。 因为输入的复杂度随其大小而增加，它通常表示为输入大小 n（以位为单位）的函数，因此复杂度是 n 的函数。 然而，对于相同大小的输入，算法的复杂性可能会有很大差异。 因此，经常使用各种复杂性函数。

最坏情况复杂度是所有​​大小为 n 的输入的所有复杂度的总和，而平均情况复杂度是所有​​大小为 n 的输入的所有复杂度的总和（这是有道理的，因为给定大小的可能输入的数量是有限）。 当使用术语“复杂度”而没有进一步定义时，考虑了最坏情况的时间复杂度。

众所周知，最坏情况和平均情况的复杂性很难正确计算。 此外，这些精确值几乎没有实际应用，因为机器或计算范式的任何变化都会稍微改变复杂性。 此外，对于较小的 n 值，资源使用并不重要，因此对于较小的 n，易于实现通常比低复杂性更有吸引力。

由于这些原因，大多数注意力都集中在高 n 的复杂性行为上，即当 n 接近无穷大时它的渐近行为。 因此，通常使用大 O 表示法来表示复杂性。

计算模型

计算模型的选择（包括指定在单位时间内执行的基本操作）对于确定复杂性至关重要。 当计算范例没有具体描述时，这有时被称为多带图灵机。

确定性计算模型是机器的后续状态和要执行的操作完全由先前状态定义的模型。 递归函数、λ演算和图灵机是最早的确定性模型。 随机存取机器（也称为 RAM 机器）是模拟现实世界计算机的流行范例。

当计算模型未定义时，通常假定为多带图灵机。 在多磁带图灵机上，大多数算法的时间复杂度与 RAM 机器上的相同，尽管可能需要相当多地关注数据在内存中的存储方式才能实现这种等效性。

可以在非确定性计算模型（例如非确定性图灵机）中的某些计算步骤中做出各种选择。 在复杂性理论中，同时考虑所有可行的选项，非确定性时间复杂度是始终做出最佳选择所需的时间量。 换句话说，计算是在所需数量的（相同的）处理器上同时完成的，非确定性计算时间是第一个处理器完成计算所花费的时间。 这种并行性可以通过在运行专门的量子算法时使用叠加的纠缠态来用于量子计算，例如 Shor 的微小整数分解。

即使这样的计算模型目前不可行，但它具有理论意义，特别是对于 P = NP 问题，该问题询问使用“多项式时间”和“非确定性多项式时间”产生的复杂度类别是否为最小上界限是一样的。 在确定性计算机上，模拟 NP 算法需要“指数时间”。 如果一项任务可以在非确定性系统上以多项式时间解决，则它属于 NP 难度类。 如果一个问题在 NP 中并且并不比任何其他 NP 问题更容易，则称它是 NP 完全的。 背包问题、旅行商问题和布尔可满足性问题都是 NP 完全组合问题。 最著名的算法对所有这些问题都具有指数复杂性。 如果这些问题中的任何一个都可以在确定性机器上在多项式时间内解决，那么所有 NP 问题也可以在多项式时间内解决，并且 P = NP 将成立。 截至 2017 年，人们普遍假设 P NP，这意味着 NP 问题的最坏情况从根本上难以解决，即在给定有趣的输入长度的情况下，所花费的时间远远超过任何可行的时间跨度（数十年）。

并行和分布式计算

并行和分布式计算涉及在同时运行的多个处理器之间划分处理。 各种模型之间的根本区别在于处理器之间发送数据的方法。 在并行计算中，处理器之间的数据传输通常非常快，而在分布式计算中，处理器之间的数据传输是通过网络完成的，因此速度要慢得多。

在 N 个处理器上的计算至少需要 N 个商在单个处理器上花费的时间。 实际上，由于某些子任务无法并行化，并且某些处理器可能需要等待另一个处理器的结果，因此永远无法达到这种理论上的理想界限。

因此，关键的复杂性问题是开发算法，以使计算时间与处理器数量的乘积尽可能接近在单个处理器上执行相同计算所需的时间。

量子计算

量子计算机是具有基于量子力学的计算模型的计算机。 Church-Turing 论点适用于量子计算机，这意味着量子计算机可以解决的任何问题也可以由图灵机解决。 然而，一些任务理论上可以使用量子计算机而不是时间复杂度显着降低的经典计算机来解决。 目前，这只是理论上的，因为没有人知道如何开发实用的量子计算机。

创建量子复杂性理论是为了研究量子计算机可以解决的不同类型的问题。 它用于后量子密码学，这是创建能够抵抗量子计算机攻击的密码协议的过程。

问题的复杂性（下限）

可能解决问题的算法的复杂性（包括未被发现的技术）的下确界就是问题的复杂性。 因此，问题的复杂性等于解决它的任何算法的复杂性。

因此，任何以大 O 表示法给出的复杂度都代表了算法和伴随问题的复杂度。

另一方面，获得问题复杂性的非平凡下限通常很困难，而且这样做的策略很少。

为了解决大多数问题，必须读取所有输入数据，这需要与数据量成正比的时间。 结果，这些问题至少具有线性复杂度，或者，在大欧米茄符号中，复杂度为 Ω(n)。

一些问题，例如计算机代数和计算代数几何中的问题，有非常大的解决方案。 因为必须写入输出，所以复杂性受输出的最大大小的限制。

排序算法所需的比较次数具有 Ω(nlogn) 的非线性下限。 因此，最好的排序算法是最有效的，因为它们的复杂度是 O(nlogn)。 事实上有 n! 组织 n 个事物的方法导致了这个下限。 因为每次比较都会划分这个 n 的集合！ 订单分成两部分，区分所有订单所需的 N 比较次数必须是 2N > n!，根据斯特林公式，这意味着 O(nlogn)。

将一个问题简化为另一个问题是获得降低复杂性约束的常用策略。

算法开发

评估算法的复杂性是设计过程的一个重要元素，因为它提供了有关预期性能的有用信息。

一个常见的误解是，由于摩尔定律预测现代计算机能力的指数增长，评估算法的复杂性将变得不那么重要。 这是不正确的，因为增加的功率允许处理大量数据（大数据）。 例如，当按字母顺序对数百个条目的列表进行排序时，任何算法都应该在不到一秒的时间内运行良好，例如一本书的参考书目。 另一方面，对于一百万个条目（例如，一个大城市的电话号码），需要 O(n2) 比较的基本算法必须执行一万亿次比较，以 10 的速度需要三个小时每秒百万次比较。 另一方面，快速排序和合并排序只需要 nlogn 比较（前者的平均复杂度，后者的最坏情况复杂度）。 对于 n = 30,000,000，这会产生大约 1,000,000 次比较，如果每秒进行 3 万次比较，这将只需要 10 秒。

因此，评估复杂性可以允许在实施之前消除许多低效的算法。 这也可以用于微调复杂的算法，而无需测试所有可能的变体。 对复杂性的研究允许通过确定复杂算法中最昂贵的步骤来集中精力提高实现的效率。