time-complexity - O(n) 和 O(log n) 的乘积是多少？

Question

正在学习归并排序算法，发现归并排序的时间复杂度为O(n log n).

想知道我们是否可以说O(n log n)= O(n) * O(log n)？

标签： time-complexitybig-omergesort

Answer 1

不，这样做没有任何意义。Big-O 函数产生函数集合，集合不能相乘。

更一般地说，您通常不会对 O(...) 结果执行任何操作。没有加法、减法、乘法。没有代数。O(...) 通常出现在证明的结论中：“根据上面的分析，我得出结论，芬克尔算法的最坏情况复杂度是 O(whatever)。” 它并没有真正出现在可能对其进行代数操作的中间。

（我想你可以执行集合操作。我从未见过有人这样做。）