0

我正在研究一个问题，为此我提出了两种算法：一种需要O(n lgn)时间，但需要额外的空间，另一种需要O(n+nlgn)时间。所以只是想问一下O(n lgn)时间复杂度是一个改进O(n+nlgn)还是两者都被认为是相等的，考虑nlgn到最大的价值。

4

1 回答 1

6

他们是一样的：

n + n lg n <= 2 n lg n   -- for n >= base of logarithm
            = O(n lg n)
于 2013-09-22T13:00:34.717 回答