我知道冒泡排序,插入排序等,但有更有效的排序算法.通过时间层次定理,对于任何实数r <2,存在可以在O(n ^ 2)中解决但在O(n ^ r)中不能解决的问题.用于证明它的结构不是很自然.什么是最有效的解决方案需要二次时间的问题的一个很好的例子？
我正在寻找具有以下品质的东西:
- 它简单易懂
- 经常使用的东西
- 可以证明O(n ^ 2)是正确解的最佳运行时间
小警告 - 输出不应该很大.(如果你想要给定列表中每对整数的总和,显然需要二次时间来输出它们).你可以假设它应该是一个决策问题,即一个肯定 - 否定答案.还让我们假设时间复杂度O(n ^ 2)是输入大小的函数,即n是表示输入所需的位数.