algorithm - n 的四次方根的复杂度函数的大 O 表示法

Question

我希望找到以下复杂函数的大 O 表示法:f(n) = n^(1/4)。

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

1. 更准确的答案似乎是O(n^1/4)。但是，由于它包含一个根，所以它不是多项式，而且我从未在任何教科书或在线资源中见过这个第 n 个根 n。<
2. 使用数学定义，我可以尝试定义一个具有指定 n 限制的上限函数。我尝试用 log2 n in blue 和 n 绘制 n^(1/4) in red 绿色。

log2 n 曲线在 n=2.361 处与 n^(1/4) 相交，而 n在 n=1 处与 n^(1/4) 相交。

根据正式的数学定义，我们可以提出两个具有不同限制的附加大 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

通常会使用复杂度函数的哪个 Big O 描述？ 3 个都“正确”吗？这取决于解释吗？

Answer 1

• 使用 O(n^1/4)非常适合大 O 符号。 Here are some examples of fractures in exponents from real life examples
• 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)) 中？如果您想练习，证明它很容易。