algorithm - 哪个具有更好的复杂性 f1 = (n+m) +(n+m)log(n+m) 或 f2 = n*m

Question

哪个函数f1或f2具有更好的时间复杂度，如果

f1 = (n + m) + (n + m) * log(n + m) 

和

f2 = n * m

标签： algorithmtime-complexity

Answer 1

这取决于. 从中选择获胜者

f1 = (n + m) + (n + m) * log(n + m) 
f2 = n * m

我们应该知道什么m和n是什么；和之间是什么关系。例如nm

保持m不变：

f1 = O((n + m) + (n + m) * log(n + m)) = O(n + n * log(n)) = O(n * log(n))
f2 = O(n * m) = O(n)

f2更好。

让m ~ n：

f1 = O((n + m) + (n + m) * log(n + m)) = O(2 * n + 2 * n * log(2 * n)) = O(n * log(n))
f2 = O(n * m) = O(n * n) = O(n**2)

现在f1是更好的选择

最后，让m ~ log(n)：

f1 = O((n + m) + (n + m) * log(n + m)) = O(n + log(n) + n*log(n + log(n))) = O(n * log(n))
f2 = O(n * m) = O(n * log(n)) = O(n * log(n))

f1并且f2具有相同的复杂性