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

Question

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

我想出了几个可能的答案。

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

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"correct"吗？靠解读吗？

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))更清楚？如果您想练习，证明它很容易。