#Recurrence T(n)=3T(n/3)+Ѳ(log₃n)

Question

抱歉，我已经尝试了很多方法来求解这个递归方程 T(n) = 3T(n/3) + Ѳ(log3n) 使用替换方法但我无法获得所需的结果：

1) T(n) = O(nlogn)

2）感应基础：对于每个 n = 1 -> 1log1 + 1 = 1 = T (1)

  Inductive step: T (k) = klogk + k for each k <n

 Use k = n / 3

T (n) = 3T (n / 3) + Ѳ (log₃n)

1) T(n) = O(nlogn)

2)归纳

 Base: for every n = 1 -> 1log1 + 1 = 1 = T (1)

  Inductive step: T (k) = klogk + k for each k <n

 Use k = n / 3

T (n) = 3T (n / 3) + Ѳ (log₃n)

= 3 [n / 3logn / 3 + n / 3] + (log₃n)

= nlogn / 3 + n + (log₃n)

= n(logn-log3) + n + (log₃n)

= nlogn-nlog3 + n + (log3n)

Answer 1

首先，我们可以（最终）忽略 Theta 表示法中的基数 3，因为它相当于一个乘法因子，因此无关紧要。那我们可以试试下面的方法：

1。检验假设：

如果我们多次将T代入自身，我们得到：

上限是多少m？我们需要假设 T(n) 有一个 停止条件 ，即 n 的某个值停止递归。假设是n = 1（其实没关系，只要是比n小很多的常数即可）。继续（并简要恢复基数 3）：

令人惊讶的是答案不是 Ө(n log n)。

2。归纳基础案例

我们不使用归纳法来证明最终结果，而是通过检查展开的行为推导出的级数结果。

对于基本情况 n / 3 = 1，我们有：

这是一致的。

3。归纳复现

同样，一致。从而归纳求和结果是正确的，T(n)确实是Ө(n).

4.数值测试：

以防万一你还是不相信它是Ө(n)，这里有一个数值测试来证明这个结果。

Javascript代码：

function T(n) {
   return n <= 1 ? 0 : 3*T(floor(n/3)) + log(n);
}

结果：

n           T(n)
--------------------------
10          5.598421959
100         66.33828212
1000        702.3597066
10000       6450.185742
100000      63745.45154
1000000     580674.1886
10000000    8924162.276
100000000   81068207.64

图表：

线性关系明确

#Recurrence T(n)=3T(n/3)+Ѳ(log₃n)

#Recurrence T(n)=3T(n/3)+Ѳ(log₃n)

recurrence