如何证明算法的运行时间界限是紧密的？

Question

如何证明算法的运行时间界限是紧密的？

algorithmcomputer-sciencebig-o

5

假设我们可以证明一个算法在输入大小为n时以时间O(f(n))运行。

我想证明这个运行时间上限是紧的。两个问题：

只需给出特定的输入，并显示运行时间至少为f(n)，这就足够了吗？
我读到一种证明收紧性的可能性是“将排序减少到它”。我不知道这是什么意思。

- 0xbadf00d

2个回答

1

广告1：是的，但你必须能够找到任何n大小的输入。一个处理9个步骤的大小为3的示例并不能真正证明什么。

广告2：如果您可以修改元素序列，使得您的算法有效地对其进行排序（在输出的某些处理后，您会得到一个排序的序列），则已将排序降低到了它。因为通过比较排序的时间复杂度不可能快于O(n log(n)), 因此可以用它来证明您的算法不能更快于O(n log(n))。

当然，为了使这个论点有效，输入和输出处理函数不能慢于或等于O(n log(n))，否则您可以对数组进行排序，并证明一个只返回输入数组的O(1)算法实际上至少是O(n log(n)) :)

- Teyras

关于1：对于任何n都不是必需的。只需证明对于所有足够大的n，存在这样的输入即可。 - kraskevich

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

“如果你是在谈论最坏情况下的复杂度，并且已经证明它运行在O(f(n))的时间复杂度，那么只要你提供一个比C*f(n)更糟糕的输入（其中C是某个常数），你就有效地证明了该算法（在最坏情况下）处于Ω(f(n))中。由于O(f(n)) [交集] Ω(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的假设是错误的，它不能在所需的时间内运行。”

“这有助于我们证明更强的主张：不仅我们的算法具有这个下限，而且所有解决特定问题的算法都具有这个下限。”