我目前正在学习大 O 表示法。在 Material 中，O(NlogN) 被描述为Doubled plus an amount proportional to N。但我认为那将是 O(N + logN) 而不是 O(NlogN) (我认为 O(NlogN) 是 双倍 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/