递归算法复杂度？

Question

我以前有以下问题：

给出递归算法T(n)，找出函数f(n)

。

注： k为常数，> 3，对于n<=1，T(N)=0E 214。

​

​

我怎样才能解决这个问题？

Answer 1

好吧，我不会展示我所有的舞步。这是你的家庭作业问题，但这里有一个概述：

基于递归定义的

• ，我们可以分解求和：

T(n) =n+T(地板(n/ k)) +T(地板(n/k^ 2)) +.+T(地板(n/ (k ^log(N)

然后，从

• ，我们可以得到一个迭代定义：

T(n) =n+地板(n/ k) +2*地板(n/k^ 2) +.+2^ (log(n) - 1) *地板(n/k^(log(N)

或

T(n) =n+和(地板(n/k^ i) *2^ (i)，i=1，log(n) )/ 2

你的问题要求大Theta。这意味着我们需要找出一个上下界。

• 上界：floor(x) <= x，所以我们放下地板，简化如下：

O ( n +n/ (k - 2) <- O(n) +(n* (2 / k) ** log(n)) / (k - 2) )

因为O(n).，最后一学期的增长肯定会比n慢，所以我们就剩下n了

Omega(n).：

• 下界：Sum(...) > 0总是这样，所以我们可以将它绑定到下面的n中，给出Sum(...) > 0

因为T既是O(f(n))，又是f(n) = n的Omega(f(n))，所以我们可以说它也是Theta(n)，所以答案是

f(n) = n

这是一个演示上、下界的程序。这个程序并不等同于一个证据，但它可以帮助你了解正在发生的事情。我按指数增长了n，所以如果你在一个对数尺度上绘制这些值，它应该会显示这些线和渐近行为。

​

const k = 4;
const logK = Math.log(k);

function T(n) {
  if (n <= 1)
   return 0;
  
  let acc = n;
  for (let i = 1; i <= Math.log(n) / logK; i++)
    acc += T(Math.floor(n * k ** -i));
  
  return acc;
}

function nonRecT(n) {
  let acc = n;
  for (let i = 1; i <= Math.log(n) / logK; i++) {
    let f = Math.floor(n * k ** -i);
    acc += f > 1 ? f * 2 ** (i - 1) : 0;
  }
  return acc;
}

for (let n = k; n <= k ** 20; n *= k) {
  console.log([
    n,
    T(n), nonRecT(n),
    n * (1.5 + 1 / (k - 2))
  ].join('\t'));
}

​