2

我们在我的算法课上讨论了主定理，对于一个问题，我试图比较 nlogn 与 1 以找出它属于 MT 的哪种情况。但我很难确定哪个更大。

编辑：这是为了解决重复问题。等式是 T(n) = 2T(n/4) + N*LogN。把它扔进去以防万一它有帮助。

4

2 回答 2

1

这样想：

  • O(N*LogN)将以N这样的方式增加，对于任何X，无论有多大，您都可以找到一个大于N的值。N*LogNX
  • O(1)将保持不变，无论是什么N。

这意味着渐近O(1)更好，即对于某些（可能非常高的）值将变得更慢。NO(N*LogN)

于 2013-02-19T01:51:33.127 回答
0

如果一个算法是 O(NlogN)，这意味着存在一个数字 A 和一个数量的执行时间 B，这样对于任何大于 A 的输入大小 N，执行时间将小于 B 乘以 NlogN。

如果一个算法是 O(1)，这意味着存在一些固定的时间量 C，无论输入大小如何，算法都可以保证完成。

在比较两种算法时，一种是 O(NlgN)，一种是 O(1)，通常会发现 O(1) 算法对于足够大的 N 值更快，但在许多情况下对于较小的 N 值，O(NlgN) 算法可能更快。

事实上，虽然像 O(N^3) 或 O(N^4) 算法这样的算法通常看起来很糟糕，但如果 N 通常为一个小数字（例如 1-5 左右）并且永远不会变得很大（即使是偶尔的 50 值也会严重影响性能）。

于 2013-02-19T02:15:14.997 回答