big-o - 我如何表达 O(n) * O(n log n)

Question

我正在写一份报告，我需要用大 O 表示法呈现一些结果。由于我以前没有使用过大 O 表示法，所以我有点不确定如何写。

我知道如果你有 O(n) * O(n) 那么结果变成 O(n^2)。例如，循环中的循环。

并且 O(n) * O(log n) 等于 O(n log n)。例如，如果您需要遍历在平衡二叉树中搜索的函数。

但是如果我必须循环一个时间复杂度为 O(n log n) 的函数。

如何正确编写 O(n) * O(n log n)？

标签： big-o

Answer 1

这只是内部任何内容的正常乘法O。

n * n*log(n) = n^2*log(n)

所以这是：

O(n^2 log n)