需要二次时间的算法任务？

Question

我知道冒泡排序、插入排序等，但还有更有效的排序算法。通过 Time Hierarchy Theorem ，对于任何实数 r < 2，有些问题可以在 O(n^2) 中解决，但不能在 O(n^r) 中解决。用于证明的结构不是很自然。最有效的解决方案需要二次时间的问题的一个很好的例子是什么？

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

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

小警告 - 输出不应该很大。 (如果你想要给定列表中每对整数的总和，显然需要二次时间来输出它们)。您可以假设它应该是 decision problem ，即回答是或否的人。我们还假设时间复杂度 O(n^2) 是输入大小的函数，即 n 是表示输入所需的位数。

Answer 1

Matrix multiplication具有 Ω(n²) 的理论下限，因为所有 n² 条目都需要处理。迄今为止最著名的算法(根据上面链接的维基百科文章)的复杂度为 O(n^2.3727)。朴素算法的复杂度为 n³。

根据关于 Computational complexity of mathematical operations 的维基百科文章, 三角矩阵的反向代入得到 n 解的时间复杂度为 O(n²)。网络上可能还有许多其他示例。

编辑:A 2014 paper by Michele Borassi, et al. , 讨论了一些可以在 O(n²) 时间内解决但不能在 O(n^2-ε) 对于任何 ε> 0。(当然，一如既往，这些结果取决于 P ≠ NP，或者，更准确地说，Strong Exponential Time Hypothesis 为真。)

他们的论文以修改后的 k-SAT problem 开头:

输入:

• 两组变量 X = {x_i}, Y = {y_j} 大小相同；
• 一组 C 这些变量的子句，这样每个子句的最大大小为 k；和
• X 和Y 的两个幂集℘(X), ℘(Y)(使用更改输入大小)。

输出 true 如果对满足所有子句的所有变量进行评估，否则为 False。

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

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

输入:X 集合和X 子集的集合C。

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