algorithm - 我认为 "NlogN"是 "N"乘以 "logN"，但为什么它被描述为 "double PLUS an amount proportional to N"

我目前正在学习大 O 符号。在 Material 中，O(NlogN) 被描述为 Doubled plus an amount proportional to N 。但我认为那将是 O(N + logN) 而不是 O(NlogN) (我认为 O(NlogN) 是 Double times logN )。

我的理解在逻辑上有问题吗？

最佳答案

将 N 替换为 2N，如下所述:
2N log 2N = 2N * (log N + log 2)(使用对数规则)

原始术语的两倍 2 * (N log N)

附加术语 (2 log 2) * N，即“与 N 成比例”。

关于algorithm - 我认为 "NlogN"是 "N"乘以 "logN"，但为什么它被描述为 "double PLUS an amount proportional to N"，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52388009/