runtime - 所有可能的排序算法分析

Question

“APS”（所有可能的排序）算法通过生成 n 元素的所有可能序列来对大小为 n 的数组 A 进行排序，并且对于每个序列，检查元素是否按排序（升序）顺序排列。

a) What is the worst-case time complexity of APS? Explain your logic / show your work.

我的答案：

最坏的情况是 O(n!)，因为它会生成所有可能的序列，然后检查是否已排序。

最好，我希望有人告诉我我是对还是错，以及如何得到答案。这个大 O 的东西让我感到困惑。

Answer 1

APS 正在生成 N 个元素的所有可能排列，这给了你 n! 不同的可能排序，所以你是正确的。

证明它是O (n!) 只需要你证明运行时是 n! 的渐近上限，这基本上意味着你必须证明：

f(n) = O(n!) 如果对于某些 m 和 c，|f(n)| < |m * n!| 对于所有 n > c。

如果你写出了实际的算法，证明这一点会更容易，但如果你遍历你的逻辑，它应该可以解决问题。