我们如何证明算法的 运行 时间限制很紧？
How can we prove that the running time bound of an algorithm is tight?
假设我们可以证明使用大小为 n 的输入调用的算法会及时运行 O(f(n))。
我想证明这个运行时间紧迫。两个问题：
- 给一个特殊的输入并显示 运行 时间至少是
f(n) 就够了吗？
- 我读到证明紧密性的一种可能性是 "reduce sorting to it"。我不知道那是什么意思
Wouldn't it suffice to give a special input and show that the running
time is at least f(n)?
是的，假设您在谈论最坏情况的复杂性。
如果您正在谈论最坏情况的复杂性 - 并且您已经证明它在 O(f(n)) 中是 运行ning，如果您发现 "worse" 比 C*f(n)) 的输入对于某个常量 C - 您有效地证明了算法（在最坏情况下的性能）在 Ω(f(n)) 中，并且由于 O(f(n)) [intersection] Ω(f(n)) = Theta(f(n))，这意味着您的算法在 运行 中 Theta(f(n)) 最坏情况分析。
注意 它实际上应该是 "family" 个示例，因为如果我声称“是的，但这仅适用于较小的 n 值，而不是 n>N（对于某些 N），你可以告诉我这一系列的例子也涵盖了 n>N 并且仍然有效的情况。
对称地，如果您证明算法具有 Ω(f(n)) 的最佳情况性能，并且您发现一些输入 运行s "better"（快）比 C*f(n))一些常数 C，你有效地证明了算法在最佳情况分析下是 Theta(f(n))。
此技巧不适用于一般情况分析 - 您应该计算 运行 时间的预期，单个示例没有帮助。
I've read that one possibility for proving the tightness is to "reduce
sorting to it". I've no idea what is meant by that
这样做是为了证明一个更有力的主张，即没有算法（根本）可以在所需时间解决某些问题。
它的常见用法是假设有一些黑盒算法A在o(g(n))时间运行s，然后使用A构建o(nlogn) 时间 运行 的排序算法。但是，由于排序是 Ω(nlogn) 的问题，我们就有了矛盾，我们可以得出关于 A 的假设是错误的，它不能在期望的时间内 运行。
这有助于我们证明一个更有力的主张：不仅我们的算法有这个下界，而且解决特定问题的所有算法都有这个下界。
ad 1.: 是的，但是你必须能够为任何 n 找到大小为 n 的输入。在 9 个步骤中处理的大小 3 的示例并不能真正证明任何事情。
广告 2.：如果您可以修改元素序列，以便您的算法对其进行有效排序（在对输出进行一些处理后，您会得到一个排序序列），那么您就减少了对它的排序。并且因为排序（通过比较）不能比 O(n log(n)) 快，这可以用来证明你的算法不能比 O(n log(n)) 快。
当然，输入和输出处理函数不能慢于或等于 O(n log(n)) 这个参数是有效的，否则你可以对数组进行排序并证明 O(1)仅 returns 输入数组的算法实际上至少为 O(n log(n)) :).
假设我们可以证明使用大小为 n 的输入调用的算法会及时运行 O(f(n))。
我想证明这个运行时间紧迫。两个问题：
- 给一个特殊的输入并显示 运行 时间至少是
f(n)就够了吗？ - 我读到证明紧密性的一种可能性是 "reduce sorting to it"。我不知道那是什么意思
Wouldn't it suffice to give a special input and show that the running time is at least f(n)?
是的，假设您在谈论最坏情况的复杂性。
如果您正在谈论最坏情况的复杂性 - 并且您已经证明它在 O(f(n)) 中是 运行ning，如果您发现 "worse" 比 C*f(n)) 的输入对于某个常量 C - 您有效地证明了算法（在最坏情况下的性能）在 Ω(f(n)) 中，并且由于 O(f(n)) [intersection] Ω(f(n)) = Theta(f(n))，这意味着您的算法在 运行 中 Theta(f(n)) 最坏情况分析。
注意 它实际上应该是 "family" 个示例，因为如果我声称“是的，但这仅适用于较小的 n 值，而不是 n>N（对于某些 N），你可以告诉我这一系列的例子也涵盖了 n>N 并且仍然有效的情况。
对称地，如果您证明算法具有 Ω(f(n)) 的最佳情况性能，并且您发现一些输入 运行s "better"（快）比 C*f(n))一些常数 C，你有效地证明了算法在最佳情况分析下是 Theta(f(n))。
此技巧不适用于一般情况分析 - 您应该计算 运行 时间的预期，单个示例没有帮助。
I've read that one possibility for proving the tightness is to "reduce sorting to it". I've no idea what is meant by that
这样做是为了证明一个更有力的主张，即没有算法（根本）可以在所需时间解决某些问题。
它的常见用法是假设有一些黑盒算法A在o(g(n))时间运行s，然后使用A构建o(nlogn) 时间 运行 的排序算法。但是，由于排序是 Ω(nlogn) 的问题，我们就有了矛盾，我们可以得出关于 A 的假设是错误的，它不能在期望的时间内 运行。
这有助于我们证明一个更有力的主张：不仅我们的算法有这个下界，而且解决特定问题的所有算法都有这个下界。
ad 1.: 是的，但是你必须能够为任何 n 找到大小为 n 的输入。在 9 个步骤中处理的大小 3 的示例并不能真正证明任何事情。
广告 2.：如果您可以修改元素序列，以便您的算法对其进行有效排序（在对输出进行一些处理后，您会得到一个排序序列），那么您就减少了对它的排序。并且因为排序（通过比较）不能比 O(n log(n)) 快，这可以用来证明你的算法不能比 O(n log(n)) 快。
当然，输入和输出处理函数不能慢于或等于 O(n log(n)) 这个参数是有效的，否则你可以对数组进行排序并证明 O(1)仅 returns 输入数组的算法实际上至少为 O(n log(n)) :).