我们如何证明算法的运行时限是紧的？

Question

假设我们可以证明一个用大小输入调用的算法n及时运行O(f(n)).

我想证明这个运行时限很紧.两个问题:

1. 提供特殊输入并显示运行时间至少是不够的f(n)？
2. 我已经读过,证明紧张的一种可能性是"减少排序".我不知道那是什么意思

Answer 1

提供特殊输入并显示运行时间至少为f(n)是否足够？

是的,假设你在谈论最坏情况的复杂性.
如果你在谈论最坏情况的复杂性 - 并且你已经证明它正在运行O(f(n)),如果你发现输入比C*f(n))某个常数"更差" C- 你有效地证明了算法(在最坏情况下性能)是?(f(n)),并且因为O(f(n)) [intersection] ?(f(n)) = Theta(f(n)),这意味着您的算法Theta(f(n))在最坏情况分析中运行.
请注意,它实际上应该是一个"家庭"的例子,因为如果我声称"是的,但这只适用于小n值,而不是n>N(对于某些人N),你可以告诉我这一系列的例子也涵盖了这个案例在哪里n>N,仍然有效.

对称地,如果你证明一个算法具有最好的案例性能?(f(n)),并且你发现某些输入比C*f(n))一些常量运行"更好"(更快)C,你有效地证明了该算法Theta(f(n))处于最佳案例分析之下.

这个技巧不适用于平均案例分析 - 你应该计算运行时的预期,而单个例子没有帮助.

我已经读过,证明紧张的一种可能性是"减少排序".我不知道那是什么意思

这样做是为了证明一个更强大的主张,即没有算法(根本没有)可以在所需的时间解决某些问题.
它的常见用法是假设有一些黑盒算法A在一段o(g(n))时间内运行,然后用于A构建一个o(nlogn)及时运行的排序算法.然而,由于排序是个?(nlogn)问题,我们有一个矛盾,我们可以得出结论A错误的假设,并且它不能在所需的时间内运行.

这有助于我们证明一个更强大的主张:不仅OUR算法具有此下限,而且解决特定问题的所有算法都具有此下限.