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

Question

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

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

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

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

Answer 1

矩阵乘法具有Ω(n ²)的理论下界,因为需要处理所有n ²个条目.迄今为止最着名的算法(根据上面链接的维基百科文章)具有复杂度O(n ^2.3727).朴素算法具有复杂度n ³.

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

编辑:Michele Borassi 等人 2014年的一篇论文.,讨论了许多决策问题(输出大小O(1)),可以在O(n ²)时间内解决,但对于任何ε > 0都不能在O(n ^{2- ε})中解决.(当然,一如既往,这些结果取决于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 ²)时间内解决.最简单的一个是子集图问题:

输入:一组X和集合ç子集X.

输出:该图ģ =(Ç,ê),其中,对于每个Ç,Ç '∈ Ç,(ç,ç ')∈ È当且仅当C ^ ⊆ Ç '.