我的函数是O(n!),还是O((n-1)!)更准确？
mon*_*ole 19 algorithm big-o time-complexity
我为旅行商问题编写了一个强力搜索算法,并对其进行了测试,以查看各种"城市"所需的时间.从下面的图中,我们可以看到,时间大约是成正比的(n-1)!地方n是"城市"的数量.它与n!(毕竟(n-1)! = n! / n)不成正比.
我的问题是,说算法运行是否仍然正确O(n!),或者说我更好O((n-1)!)吗？我以前从未见过后者,但似乎更准确.看来我在这里误解了一些东西.
[t =所用时间,n =城市数量]
Sve*_*ach 48
根据定义,O(f(n))是由f(n)渐近支配的所有函数的集合,即具有常数C和n_0的所有函数g(n)的集合,使得
g(n) < C * f(n) for all n > n_0
根据这个定义,O(n!)实际上是O((n-1)!)的超集,因为函数f(n)= n!是第一组的成员,但不是第二组的成员.这两套实际上并不相同.
但是,说你的问题是O(n!)是正确的,因为这只是一个上边界.说你的问题是Θ(n!)是不正确的,因为这表示直到常数因子的精确渐近行为.
在实践中没有太大的区别,并且,如另一个答案所述,您可以将n重新定义为减去一个城市的数量.
- 对.我不太同意`f(n)`和`f(n-1)`之间的"实践中没有大的区别" - 当函数的增长速度和阶乘一样快时!IOW,可以说任何Θ(_n_!)算法仅适用于非常小的输入; 你永远不会有机会让'n`变得如此之大,以至于一个或多或少是微不足道的. (5认同)
O(n!)够好了.n大或n-1没有区别n.
有关 示例,请参阅https://www.wikiwand.com/en/Time_complexity#/Table_of_common_time_complexities.
- 它们都"像地狱一样大,无论如何都不适用于大n".所以,确实没有区别:)这两个数字都大于宇宙中估计的原子数(仅为10 ^ 81). (22认同)
- @ jbsu32,这只是废话.`O(...)`是一类函数,不能等于数.是的,'O(10n)= O(n)`,所以'O`-符号在'39.9百万'和'360万'之间没有区别. (17认同)
- @ jbsu32,O(10n)总是等于O(n),因为我们不关心常数因子 (5认同)
- @ jbsu32,`O(f(n))`是一类函数*,就像偶数或可微函数一样.什么完全属于这个类由斯文(或在数学书籍)解释.如果我们将类视为属于这个类的所有函数的集合(常见概念),那么是,"O(10n)= O(n)= O(10 ^ 100n)",因为它们的元素是相同的. (4认同)
- 比如,一个大的值是'n = 100`,然后是'O(n!)= 9.33*10 ^ 157`,其中`O((n-1)!)= 9.33*10 ^ 155`.你觉得这两个没什么区别吗？:) (3认同)
- “它们都‘大得像地狱一样，无论如何都无法用于大 n’’” - 这并不意味着它们没有任何区别：D (2认同)
| 归档时间： |
|
| 查看次数： |
4119 次 |
| 最近记录： |