python - Big-O 表示法，Python - 如何正确展开 "5 + n(mlogm + 21)"

Question

我正在编写一个Python定义，它有一个O(n)的for循环，但在它内部使用了Python中的list.sort()定义，它有O(n log n)..

我最终得到的时间复杂度为 - 5 + n(mlogm + 21)

我不确定如何将其转换为 Big-O，因为从长远来看，mlogm 显然是最坏的情况，但在 for 循环内，我不确定如何得出正确的答案.

Answer 1

“大O”的定义如下:f(n) = O(g(n)) 表示存在正常数 c 和 k，使得 0 ≤ f(n) ≤ cg(n) 对于所有 n ≥ k。也就是说，对于上面的示例，它应该是 O(n(mlog(m)))，假设 m > 1。

如果 m == 1，则 log(m) == 0，因此表示法应为 O(n)。如果两者都可行，您可能需要考虑使用 O(nmlog(m) + n))