正在学习归并排序算法,发现归并排序的时间复杂度是O(n log n)
。
想知道是否可以说O(n log n)
= O(n) * O(log n)?
正在学习归并排序算法,发现归并排序的时间复杂度是O(n log n)
。
想知道是否可以说O(n log n)
= O(n) * O(log n)?
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
为零时除以零。实际上,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