计算T(n)的复杂度? [英] Calculate Complexity of T(n)?

问题描述

给出::对于某些 a (我将 T(n)= T(n/10)+ T(an)+ n 不知道它的值)，并且: T(n)= 1 ，如果 n<10 .

Given: T(n) = T(n/10) + T(an) + n for some a (which I know nothing about its value), and that: T(n) = 1 if n < 10.

我想检查以下情况是否可能(对于某些 a 值，我想找到最小的 a ):

I want to check if the following is possible (for some a values, and I want to find the smallest possible a):

对于每个 c>0 中有 n 0 >0 ，这样对于每个 n>n 0 ， T(n)> = c * n 或换句话说T(n)= omega(n)

For every c > 0 there is n0 > 0 such that for every n > n0, T(n) >= c * n Or in other words T(n)=omega(n)

感谢您的帮助.

推荐答案

假设<9/10.令c = max(1/(9/10-a)，1)，使得c≥1和1/c≤9/10-a.那么对于1≤n<10，

Suppose that a < 9/10. Let c = max(1/(9/10 - a), 1), so that c ≥ 1 and 1/c ≤ 9/10 - a. Then for 1 ≤ n < 10,

T(n) = 1 ≤ n ≤ cn.

归纳地，对于n≥10，

Inductively, for n ≥ 10,

T(n)
= T(n/10) + T(an) + n
≤ cn/10 + can + n
= c(1/10 + a + 1/c)n
≤ c(1/10 + a + 9/10 - a)n
= cn.

现在假设a = 9/10.对于1≤n<10，我们知道log10 n<1，因此

Now suppose that a = 9/10. For 1 ≤ n < 10, we know log10 n < 1 and therefore

T(n) = 1 > n log10 n - n.

归纳地，对于n≥10，

Inductively, for n ≥ 10,

T(n)
= T(n/10) + T(9n/10) + n
> (n/10) log10 (n/10) - (n/10) + (9n/10) log10 (9n/10) - (9n/10) + n
= (n/10) log10 (n/10) + (9n/10) log10 (9n/10)
> (n/10) log10 (n/10) + (9n/10) log10 ( n/10)
= (n/10) (log10 n - 1) + (9n/10) (log10 n - 1)
= n log10 n - n.

给出c>0，选择n0，使log10 n0-1 = c，即n0 = exp10(c + 1).那么对于所有n>n0，

Given c > 0, pick n0 such that log10 n0 - 1 = c, i.e., n0 = exp10(c + 1). Then for all n > n0,

T(n) > n log10 n - n = n(log10 n - 1) > n(log10 n0 - 1) = cn.

这篇关于计算T(n)的复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！