下图所示的以下函数的渐近复杂度的递增顺序为:
The increasing order of following functions shown in the picture below in terms of asymptotic complexity is:
(A)f1(n); f4(n); f2(n); f3(n)
(A) f1(n); f4(n); f2(n); f3(n)
(B)f1(n); f2(n); f3(n); f4(n);
(B) f1(n); f2(n); f3(n); f4(n);
(C)f2(n); f1(n); f4(n); f3(n)
(C) f2(n); f1(n); f4(n); f3(n)
(D)f1(n); f2(n); f4(n); f3(n)
(D) f1(n); f2(n); f4(n); f3(n)
a)这个简单问题的时间复杂度顺序为--->(n ^ 0.99)*(logn)< n ......怎么样? log可能是一个缓慢增长的函数,但它仍然比常数增长
a)time complexity order for this easy question was given as--->(n^0.99)*(logn) < n ......how? log might be a slow growing function but it still grows faster than a constant
b)考虑函数f1假设它是f1(n)=(n ^ 1.0001)(logn )那么答案是什么?
b)Consider function f1 suppose it is f1(n) = (n^1.0001)(logn) then what would be the answer?
何时存在涉及对数和多项式表达式相乘的表达式,对数函数是否超过多项式表达式?
whenever there is an expression which involves multiplication between logarithimic and polynomial expression , does the logarithmic function outweigh the polynomial expression?
c)在这种情况下如何检查
c)How to check in such cases suppose
1)(n ^ 2)logn vs(n ^ 1.5)其中时间复杂度更高? 2)(n ^ 1.5)登录与(n ^ 2)登录哪个时间复杂度较高?
1)(n^2)logn vs (n^1.5) which has higher time complexity? 2) (n^1.5)logn vs (n^2) which has higher time complexity?
推荐答案如果我们认为C_1和C_2使得C_1< C_2,那么我们可以肯定地说以下内容
If we consider C_1 and C_2 such that C_1 < C_2, then we can say the following with certainty
(n^C_2)*log(n) grows faster than (n^C_1)这是因为(n ^ C_1)的增长慢于(n ^ C_2 )(显然)
This is because (n^C_1) grows slower than (n^C_2) (obviously)
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)具有更大的复杂度(n)作为缓慢增长的功能,但它的增长速度仍然快于1,这是关键。
We think of log(n) as a "slowly growing" function, but it still grows faster than 1, which is the key here.
coder101在评论中提出了一个有趣的问题,
coder101 asked an interesting question in the comments, essentially,
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)的the的值。
In order to do this, let us find the value of ϵ that satisfies n^ϵ > log_d(n).
n^ϵ > log_d(n) ϵ*ln(n) > ln(log_d(n)) ϵ > ln(log_d(n)) / ln(n)因为我们知道这样的事实
Because we know for a fact that
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.有了这些知识,我们可以说
With this knowledge, we can say that
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.更多推荐
典型表达式的渐近复杂度
发布评论