n的第四个根的复杂性函数的大O表示法

Question

我期望找到以下复杂功能的Big O表示法:f(n) = n^(1/4).

我想出了一些可能的答案.

1. 似乎更准确的答案O(n^1/4).然而,因为它包含了根,它不是一个多项式,我从来没有见过这种ñ "日根植n在任何教科书或在线资源.
2. 使用数学定义,我可以尝试定义具有指定n限制的上限函数.我尝试用蓝色和绿色绘制n^(1/4) 红色.log2 n n

该log2 n曲线与相交n^(1/4)处n=2.361,而n与相交n^(1/4)处n=1.

鉴于正式的数学定义,我们可以提出另外两个具有不同限制的Big O符号.

以下显示O(n)适用于n > 1.

f(n) is O(g(n))
Find c and n0 so that
n^(1/4) ? cn 
where c > 0 and n ? n0
C = 1 and n0 = 1
f(n) is O(n) for n > 1

这个显示O(log2 n)适用于n > 3.

f(n) is O(g(n))
Find c and n0 so that
n^(1/4) ? clog2 n 
where c > 0 and n ? n0
C = 1 and n0 = 3
f(n) is O(log2 n) for n > 3

通常会使用哪种大O复杂功能描述？都是3"正确"吗？这取决于解释吗？

Answer 1

• 使用O(n^1/4)对于大O符号来说非常好.以下是现实生活中的指数中的裂缝的一些例子
• O(n)也是正确的(因为大O只给出上限),但它不紧,所以n^1/4是O(n),但不是Theta(n)
• n^1/4不在O(log(n))(证据指南如下).

对于任何价值r>0,以及足够大的价值n,log(n) < n^r.

证明:

看看 log(log(n))和r*log(n).对于足够大的值,第一个明显小于第二个.在大O表示法的术语,我们可以确定地说,该r*log(n))不是在O(log(log(n))和log(log(n))是⁽¹⁾ ,因此,我们可以说:

log(log(n)) < r*log(n) = log(n^r)     for large enough values of n

现在,用基数指数每一边e.请注意,左手和右手的值都是正值足够大n:

e^log(log(n)) < e^log(n^r)
log(n) < n^r

此外,以类似的方式,我们可以显示任何常量c,以及足够大的值n:

c*log(n) < n^r

因此,根据定义,它意味着n^r不在O(log(n)),并且您的具体情况:n^0.25不在O(log(n)).

脚注:

(1)如果你仍然不确定,创建一个新的变量m=log(n),是明确比r*m不O(log(m))？如果你想锻炼,证明这很容易.