首页 > 代码库 > [Algorithm] Asymptotic Growth Rate
[Algorithm] Asymptotic Growth Rate
f(n) 的形式 vs 判定形势
但,此题型过于简单,一般不出现在考题中。
Extended:
link
Let‘s set n = 2^m, so m = log(n)
T(n) = 2*T(n^(1/2)) + 1 =>
T(2^m) = 2*T(2^(m/2)) + 1 =>
S(M) = 2*S(M/2)) + 1
通过变量替换,变为了熟悉的、主定理能解决的 形式 => S(m) ~ O(m)
故,S(m) = T(log(n)) ~ O(log(n))
link
关键点:match 主定理(3)的条件。
a*f(n/b) <= c*f(n) ->
3*f(n/4) <= c*f(n) ->
3*(n/4)*log(n/4) <= c*n*log(n) ->
3/4 * n*log(n/4) <= c*n*log(n)
可见,有c<1时,是满足的。
答案就是O(nlogn)
When f(x) = x*sqrt(x+1)
这里的常数1是个tricky.
去掉它,x^(3/2)
变为x,sqrt(2)*[x^(3/2)]
可见,f(x)~Θ(x^(3/2))
T(n)=T(⌊n/2⌋)+T(⌊n/4⌋)+T(⌊n/8⌋)+n.
link
n+(7/8)*n+(7/8)^2 *n+(7/8)^3 *n+? 等比数列!
so we have a geometric series and thus,
for our upper bound.
In a similar way, we could count just the contribution of the leftmost branches and conclude that T(n)≥2n.
Putting these together gives us the desired bound, T(n)=Θ(n)
Extended:
Recurrence Relation T(n)=T(n/8)+T(n/4)+lg(n)
太难:Solution.
[Algorithm] Asymptotic Growth Rate