9

我知道冒泡排序、插入排序等，但有更有效的排序算法。根据时间层次定理，对于任何真正的 r < 2，存在可以在 O(n^2) 中解决但在 O(n^r) 中无法解决的问题。用于证明的构造不是很自然。什么是最有效的解决方案需要二次时间的问题的一个很好的例子？

我正在寻找最好具有以下品质的东西：

  • 简单易懂
  • 经常使用的东西
  • 可以证明 O(n^2) 是正确解的最佳运行时间

小警告 - 输出不应该很大。（如果您想要给定列表中每对整数的总和，显然需要二次时间来输出它们）。您可以假设它应该是一个决策问题，即一个有“是”或“否”答案的问题。还让我们假设时间复杂度 O(n^2) 是输入大小的函数，即 n 是表示输入所需的位数。

4

3 回答 3

8

矩阵乘法的理论下限为 Ω( n 2 )，因为需要处理所有n 2个条目。迄今为止最著名的算法（根据上面链接的 Wikipedia 文章）的复杂度为 O( n 2.3727 )。朴素算法的复杂度为 n 3。

根据关于数学运算的计算复杂性的维基百科文章，三角矩阵的反向替换以获得n 个解是 O( n 2 )。网络上可能还有许多其他示例。

编辑：Michele Borassi等人在 2014 年发表的一篇论文。, 讨论了许多决策问题（输出大小 O(1)），对于任何ε > 0，这些问题可以在 O( n2 ) 时间内解决，但在 O( n2 - ε ) 时间内无法解决。 （当然，与往常一样，这些结果取决于 P ≠ NP，或者更准确地说，强指数时间假设是正确的。）

他们的论文以修改后的k -SAT 问题为开端：

输入：

  • 两组相同大小的变量X = { x i }, Y = { y j }；
  • 在这些变量上的一组C子句，使得每个子句的大小最多为k；和
  • X和Y的两个幂集℘( X )、℘( Y ) （用于更改输入大小）。

输出： true如果所有变量的评估都满足所有子句，False否则。

请注意，未修改的k -SAT 问题（输入不包括上面的第三个项目符号）是 NP 完全的，因此通常将其视为指数时间问题。然而，这里的输入大小本身是变量数量的指数。他们表明，通过这种修改，问题总是可以在二次时间内解决（只需尝试所有可能的评估）。对于这个答案更重要的是，他们还表明这是解决问题的任何算法的最小时间复杂度。

有人可能会反对说这个修改后的k -SAT 问题很自然。然而，他们随后用它来表明许多其他看起来确实很自然的问题也无法在少于 O( n 2 ) 的时间内解决。最简单的一个是子集图问题：

输入：一个集合X和一个X子集的集合C。

输出：图G = ( C , E )，其中，对于每个C，C ′ ∈ C， ( C , C ′) ∈ E当且仅当C ⊆ C ′。

于 2012-12-16T07:07:01.217 回答
1

您在混合计算模型方面犯了一个根本性错误。

时间层次定理是关于图灵机的，而大多数其他界限要么有自己的模型（如排序的比较模型），要么通常与 RAM 模型有关。

所以真正的问题是，你说的是哪种计算模型？

此外，谈论不比 O(n^2) (BigOh) 差的最佳算法是无稽之谈。BigOH 是一个上限。您可能打算使用 Theta。

于 2012-12-16T18:22:13.740 回答
1

这已经是将近一年之后了，但我想我有一个答案：偏序发现。

考虑一下对总排序进行排序。您有一个由 n 个对象组成的序列（我们假设它们是不同的），以及一个比较操作，它测试两个元素以查看一个是否小于或等于另一个。

您正在尝试发现元素所在的排列。有 n! 可能的排列，所以你试图发现一个介于 1 和 n 之间的数字！每次比较都会为您提供一点信息。发现一个介于 1 和 n 之间的数！需要发现 log(n!) 位。因此，所需的比较次数也是 log(n!) 位，或者：

log(n!) = n log n + o(n log n) = Ω(n log n) 位

（当然，所有对数都以 2 为底。）

你不能做得比这更好。如果每个查询都为您提供一位信息，并且您需要发现至少 Ω(n log n) 位，那么您需要 Ω(n log n) 比较。如果您认为自己可以做得更好，请与 Shannon、Chaitin 和 Kolmogorov 一起讨论。

但更好的是，已知算法即使在最坏的情况下也能做到（例如堆排序）。从这个意义上说，堆排序是渐近最优的。

（请注意，如果您有一个返回多于一位信息的查询操作，您可以做得更好。例如，如果您能想出一个返回 Ω(log n) 位的查询操作，那么您应该能够以 Ω 排序(n) 时间。有关详细信息，请参阅基数排序。）

这种分析适用于各种算法。在 n 个事物的序列中找到一个事物需要发现一个介于 1 和 n 之间的数字，这意味着发现 log n + O(1) 位。如果您的查询操作返回一位，则需要 Ω(log n) 个查询来进行搜索。（有关详细信息，请参阅二进制搜索。）

我想你可以看到我要去哪里。

现在假设您有 n 个元素，它们具有偏序关系，但您不知道它是什么并且想要找出。但是，您所拥有的是一个比较两个元素 x 和 y 的查询，如果 x 在偏序中小于或等于 y，则返回“true”。

有一个明显的算法可以发现需要 Ω(n^2) 时间的偏序：只需将每个元素与其他元素进行比较。

但这是最优的吗？好吧，查询操作返回一位信息。n 个元素的偏序数由Sloane 的 A001035 给出。如果我没看错的话，这个序列是 Ω(2^(n^2))，这意味着要发现一个偏序，你需要：

Ω(log 2^(n^2)) = Ω(n^2) 位

也就是说，你不能比 Ω(n^2) 时间做得更好，所以这是一个渐近最优算法。

“所以”，我听到你问，“我相信输入的大小是 n。但输出的大小不是O(n^2)，所以它实际上是某种深层技术意义上的线性算法？”

也许。我现在真的没有时间详细介绍，但我会用一个问题来回答它。

在普通旧排序的情况下，我们可能会得到 n 个不同的元素。要区分它们，需要用 n 个不同的标签来标记它们。存储 n 个不同的标签意味着存储 n 个数字，每个数字都在 1 和 n 之间。这些数字中的每一个都需要 log n 位来表示它，因此问题的总大小是 n log n bits。那么为什么我们不说堆排序在问题的大小上是线性的呢？

于 2013-10-01T05:36:06.757 回答