我的函数是 O(n!)，还是 O((n-1)!) 更准确？
Is my function O(n!), or is O((n-1)!) more accurate?
我已经为旅行商问题编写了一个蛮力搜索算法，并对其进行了测试以查看不同数量的 'cities' 所花费的时间。从下图中，我们可以看出时间大致与 (n-1)! 成正比，其中 n 是 'cities' 的数量。和n!不成正比（毕竟(n-1)! = n! / n）。
我的问题是，说算法在 O(n!) 中运行是否仍然正确，还是我说 O((n-1)!) 更好？我以前从未见过后者，但它似乎更准确。看来我理解错了。
[t = 所用时间，n = 城市数]
O(n!) 就够了。 n 或 n-1 对大 n 没有影响。
见https://www.wikiwand.com/en/Time_complexity#/Table_of_common_time_complexities
举些例子。
根据定义，O(f(n))是所有渐近地由f(n)支配的函数的集合，即所有函数g(n)的集合，其中有常数C和n_0 这样
g(n) < C * f(n) for all n > n_0
根据这个定义，O(n!) 实际上是 O((n-1)!) 的 超集，因为函数 f(n) = n！是第一组的成员，但不是第二组的成员。这两组实际上并不相同。
不过，说你的问题是 O(n!) 是正确的，因为这只说明了一个上限。说您的问题是 ϴ(n!) 是不正确的，因为这表示直到常数因子的精确渐近行为。
实践中没有太大区别，而且，如另一个答案中所述，您可以重新定义 n 表示城市数减去一个。
你可以简单地证明为：
O((n-1)!)表示存在常数c如：
算法步骤（或者时间复杂度）< c (n-1)！ < c n!/n < c n!对于每个 n>1 .
因此，由于您的算法复杂度函数成立：
算法步骤（或时间复杂度）
你的算法也是 O(n!)。
所以我们证明如果你算法的时间复杂度是O((n-1)!)那么它也是O(n!)。
Sven Marnach 的回答非常好，我只想详细说明一下这部分：
or is it better for me to say O((n-1)!)?
正如其他人所说，O(n) 通常就足够了。如果你确实想进一步了解这个问题，你可以尝试找到并证明：
- 下限（通常表示为
Ω(n)）
- 严格的上限
下界基本上是说，在某些渐近条件下，不可能有更快地渐近求解问题的算法。紧上限是与下限相匹配的上限，即您必须证明下限 Ω(f(n)) 和上限 O(f(n))。如果你能证明一个下界和一个紧的上界，就意味着你的算法是该问题的渐近最优算法。
为此举一个具体的例子：你肯定知道像归并排序或快速排序这样的排序算法以及它们的上限O(n log n))。 Donald Knuth（几十年前）表明，基于比较的整数排序算法至少需要 n log n 次比较，即 Ω(n log n) 次操作。由于我们有一个匹配的上限，合并排序和快速排序都被认为是渐近最优的（尽管它们的性能在实践中有很大差异）。
我已经为旅行商问题编写了一个蛮力搜索算法，并对其进行了测试以查看不同数量的 'cities' 所花费的时间。从下图中，我们可以看出时间大致与 (n-1)! 成正比，其中 n 是 'cities' 的数量。和n!不成正比（毕竟(n-1)! = n! / n）。
我的问题是，说算法在 O(n!) 中运行是否仍然正确，还是我说 O((n-1)!) 更好？我以前从未见过后者，但它似乎更准确。看来我理解错了。
[t = 所用时间，n = 城市数]
O(n!) 就够了。 n 或 n-1 对大 n 没有影响。
见https://www.wikiwand.com/en/Time_complexity#/Table_of_common_time_complexities 举些例子。
根据定义，O(f(n))是所有渐近地由f(n)支配的函数的集合，即所有函数g(n)的集合，其中有常数C和n_0 这样
g(n) < C * f(n) for all n > n_0
根据这个定义，O(n!) 实际上是 O((n-1)!) 的 超集，因为函数 f(n) = n！是第一组的成员，但不是第二组的成员。这两组实际上并不相同。
不过，说你的问题是 O(n!) 是正确的，因为这只说明了一个上限。说您的问题是 ϴ(n!) 是不正确的，因为这表示直到常数因子的精确渐近行为。
实践中没有太大区别，而且，如另一个答案中所述，您可以重新定义 n 表示城市数减去一个。
你可以简单地证明为：
O((n-1)!)表示存在常数c如：
算法步骤（或者时间复杂度）< c (n-1)！ < c n!/n < c n!对于每个 n>1 .
因此，由于您的算法复杂度函数成立： 算法步骤（或时间复杂度）
你的算法也是 O(n!)。
所以我们证明如果你算法的时间复杂度是O((n-1)!)那么它也是O(n!)。
Sven Marnach 的回答非常好，我只想详细说明一下这部分：
or is it better for me to say O((n-1)!)?
正如其他人所说，O(n) 通常就足够了。如果你确实想进一步了解这个问题，你可以尝试找到并证明：
- 下限（通常表示为
Ω(n)） - 严格的上限
下界基本上是说，在某些渐近条件下，不可能有更快地渐近求解问题的算法。紧上限是与下限相匹配的上限，即您必须证明下限 Ω(f(n)) 和上限 O(f(n))。如果你能证明一个下界和一个紧的上界，就意味着你的算法是该问题的渐近最优算法。
为此举一个具体的例子：你肯定知道像归并排序或快速排序这样的排序算法以及它们的上限O(n log n))。 Donald Knuth（几十年前）表明，基于比较的整数排序算法至少需要 n log n 次比较，即 Ω(n log n) 次操作。由于我们有一个匹配的上限，合并排序和快速排序都被认为是渐近最优的（尽管它们的性能在实践中有很大差异）。