algorithm - 当时间复杂度为 O(n!) 和 O(2^n) 时？

Question

我正在练习算法，但总是对 O(n!) 和 O(2^n) 之间的时间复杂度感到困惑。我知道 O(2^n) 可以理解为从集合中选择或不选择一个项目，这通常喜欢递归(或回溯？)情况。但回溯问题有时也标有 O(n!)？

有人可以用简单的语言解释一下吗？

Answer 1

大 O 表示法不会产生准确的结果，而是通过指定一些上限函数来估计函数的增长。为了表示此类函数中最相关的族，常用的术语有对数、线性、多态和指数。 O(n!) 和 O(2^n) 都属于指数增长的范畴。只是 O(n!) 增长稍快。

因此，作为外卖结论，Big O 允许有些草率，偶尔会有一些函数更接近上限，但不同的作者可能会使用任何一个术语来指代相同的算法。

在回溯时，每一步中的解决方案选择可能会受到上一步中所做选择的限制，因此每一步中可能的选择数量都会按照阶乘模式减少一个。但并非所有回溯的情况都属于这一类，如果每一步中的解决方案选择独立于之前的步骤，有些情况可能涉及复杂度 O(2^n) 甚至 O(n^n)。

编辑:更正了 O(2^n)、O(n!) 和 O(n^n) 之间的增长关系