典型表达式的渐近复杂度

Question

下图所示函数的渐近复杂度递增顺序为：

(A) f1(n); f4(n); f2(n); f3(n)

(B) f1(n); f2(n); f3(n); f4(n);

(C) f2(n); f1(n); f4(n); f3(n)

(D) f1(n); f2(n); f4(n); f3(n)

a)这个简单问题的时间复杂度顺序为--->(n^0.99)*(logn) < n ......怎么办？ log 可能是一个增长缓慢的函数，但它仍然比常量增长得更快

b)考虑函数 f1 假设它是 f1(n) = (n^1.0001)(logn) 那么答案是什么？

每当有一个表达式涉及对数和多项式之间的乘法时，对数函数是否大于多项式表达式？

c)在这种情况下如何检查假设

1)(n^2)logn vs (n^1.5) 哪个时间复杂度更高？ 2) (n^1.5)logn vs (n^2) 哪个时间复杂度高？

Answer 1

如果我们考虑C_1和C_2使得C_1 < C_2，那么我们可以肯定地说

(n^C_2)*log(n) grows faster than (n^C_1)

这是因为 (n^C_1) 比 (n^C_2) 增长慢（显然）

also, for values of n larger than 2 (for log in base 2), log(n) grows faster than 
1.

in fact, log(n) is asymptotically greater than any constant C,
because log(n) -> inf as n -> inf

if both (n^C_2) is asymptotically than (n^C_1) AND log(n) is asymptotically greater 
than 1, then we can certainly say that 
(n^2)log(n) has greater complexity than (n^1.5)

我们将 log(n) 视为一个 "slowly growing" 函数，但它仍然比 1 增长得更快，这是这里的关键。

coder101 在评论中提出了一个有趣的问题，本质上，

is n^e = Ω((n^c)*log_d(n))?
where e = c + ϵ for arbitrarily small ϵ

让我们做一些代数。

n^e = (n^c)*(n^ϵ)
so the question boils down to
is n^ϵ = Ω(log_d(n))
or is it the other way around, namely:
is log_d(n) = Ω(n^ϵ)

为了做到这一点，让我们找到满足 n^ϵ > log_d(n) 的 ε 值。

n^ϵ > log_d(n)
ϵ*ln(n) > ln(log_d(n))
ϵ > ln(log_d(n)) / ln(n)

因为我们知道一个事实

ln(n) * c > ln(ln(n))        (1)
as n -> infinity

We can say that, for an arbitrarily small ϵ, there exists an n large enough to 
satisfy ϵ > ln(log_d(n)) / ln(n)

because, by (1), ln(log_d(n)) / ln(n) ---> 0 as n -> infinity.

有了这些知识，我们可以说

is n^ϵ = Ω(log_d(n))
for arbitrarily small ϵ

which means that
n^(c + ϵ) = Ω((n^c)*log_d(n))
for arbitrarily small ϵ.

通俗地说

n^1.1 > n * ln(n)
for some n

also

n ^ 1.001 > n * ln(n)
for some much, much bigger n

and even
n ^ 1.0000000000000001 > n * ln(n)
for some very very big n.

Answer 2

将 f1 = (n^0.9999)(logn) 替换为 f1 = (n^1.0001)(logn) 将得到答案 (C)：n, (n^1.0001)(logn), n^2, 1.00001 ^n

推理如下：

。 (n^1.0001)(logn) 的复杂度比n高，显而易见。

。 n^2 高于 (n^1.0001)(logn) 因为多项式部分渐近支配对数部分，所以高阶多项式 n^2 胜出

。 1.00001^n 优于 n^2，因为 1.00001^n 呈指数增长，而 n^2 呈多项式增长。指数增长渐近获胜。

顺便说一句，1.00001^n 看起来有点类似于称为 "sub-exponential" 增长的族，通常表示为 (1+Ɛ)^n。尽管如此，无论 Ɛ 很小，次指数增长仍然主导任何多项式增长。

Answer 3

这个问题的复杂度介于 f1(n) 和 f2(n) 之间。

对于f(n) = n ^ c where 0 < c < 1，曲线增长最终会变得如此缓慢，以至于与线性增长曲线相比变得如此微不足道。

对于f(n) = logc(n), where c > 1，曲线增长最终会变得如此缓慢，以至于与线性增长曲线相比变得如此微不足道。

这样两个函数的乘积，与线性增长曲线相比，最终也会变得微不足道。

因此，Theta(n ^ c * logc(n)) 比 Theta(n) 渐近复杂。

典型表达式的渐近复杂度

Asymptotic complexity for typical expressions

time-complexity

asymptotic-complexity