O(n)和O(log n)的乘积是什么？

Question

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

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

- user14673850

Answer 1

不，这样做没有意义。大O函数产生一组函数，而集合不能相乘。

更一般地说，通常不对O(...)结果执行任何操作。不能将它们相加、相减或相乘。没有代数。O(...)通常出现在证明的结论中：“根据以上分析，我得出Finkle算法的最坏情况复杂度是O(某些内容)。” 它实际上不会在中间显示，也不可能进行代数运算。（我想你可以执行集合运算，但我从未见过有人这样做。）

- John Kugelman

Answer 2

为了明确做 O(n) * O(log n) 是什么意思，我们定义如下：

如果一个函数 f 可以被写成 f(n) = g(n) h(n) 的形式，其中 g 属于 O(n)，h 属于 O(log n)，那么该函数 f 就属于 O(n) * O(log n)。

现在我们可以证明集合 O(n) * O(log n) 等同于集合 O(n log n)，因为它们的函数是相同的。

• 给定g在O(n)和h在O(log n)，存在N_g，c_g，N_h，c_h使得对于所有n >= max(N_g, N_h)，我们有|g(n)| <= c_g n和|h(n)| <= c_h log n。由此可知，|g(n) h(n)| <= c_g c_h n log n，因此max(N_g, N_h)和c_g c_h足以证明f在O(n log n)中。
• 反之，给定f在O(n log n)，存在N_f >= 1，c_f使得对于所有n >= N_f，|f(n)| <= c_f n log n。定义g(n) = max(1, n)和h(n) = f(n) / max(1, n)；显然，g在O(n)中，我们还可以看到对于n >= N_f，我们有|h(n)| <= c_f n log n / max(1, n)，其中右侧的边界等于c_f log n，因为n >= 1，所以N_f，c_f足以证明h在O(log n)中。由于我们有f(n) = g(n) h(n)，因此根据定义，f在O(n) * O(log n)中。

选择 N_f >= 1 和 g(n) = max(1, n) 是为了避免在 n 为零时除以零。

- kaya3

Answer 3

实际上，Big-O的定义不是可交换的，让我们看一个例子：

假设f被定义为f(n) = n

f(n) = O(n^2) & f(n) = O(n^3)，但O(n^2) != O(n^3)

这是因为使用“等号=”在这里并不能准确地定义，我们应该说f(n)是O(g)。

无论如何，稍微不准确一点，这里是sipser抓取的Big-O定义：

如果存在正整数c和n0，使得对于每个整数n≥n0，都有f(n) ≤ c g(n)，则称f(n) = O(g(n))。
当f(n) = O(g(n))时，我们说g(n)是f(n)的一个上界，或者更精确地说，g(n)是f(n)的渐近上界，以强调我们正在忽略常数因素。

因此，为了证明你所说的，你必须首先定义方程中*的含义，并且对于每个O(n log n)的函数，都要显示它也是O(n) * O(log n)，反之亦然。

但是，如果再次不准确地将*定义为符号多项式乘法，则对于某些正常数c和d，我们有以下结果。

O(n log n) = O(cn log n) = O(log n ^ (cn)) = O(d log n^(cn)) = O(log (n^cn) ^ d) = O(log n^cdn) ~= log n ^ cdn ~= cdn * log n

= O(n) * O(log n) = O(cn) * O(d log n) = O(cn) * O(log n^d) ~= cn * (log n^d) ~= cn * d*logn ~= cdn * log n

- amirhe