algorithm - hanoi的max、ruler、tower的递归算法分析

Question

我有以下 robert sedwick 的 C++ 算法程序

Item max(Item a[], int l, int r){
    if (l == r) return a[l];
    int m = (l+r)/2; 
    Item u = max(a, l, m);
    Item v = max(a, m+1, r);
    if (u > v) 
        return u; 
    else 
        return v;
}

以下是汉诺塔的程序

void hanoi(int N, int d)
  {
    if (N == 0) return;
    hanoi(N-1, -d);
    shift(N, d);    
    hanoi(N-1, -d);
  }  

下面是尺子程序

void rule(int l, int r, int h)
  { int m = (l+r)/2;
    if (h > 0)
      { 
        rule(l, m, h-1);
        mark(m, h);
        rule(m, r, h-1);
      }
  }

以上三个问题都是通过将大小为2的n次方的问题分成两个大小为2的n-1次方的问题来求解的。

我理解 ruler 和 max，但是上面语句中的 towerof hanoi 呢？

在分析上述程序时，提到作者为了找到最大值，我们在输入的大小上有线性时间解决方案；对于绘制标尺和求解塔，我们有输出大小的线性时间解决方案。

作者所说的输出大小的线性时间解决方案是什么意思？

Answer 1

对于 honoi 塔，您的递归算法是 (H(1) = 1):

H(n) = 2 H(n-1) + 1 = 2^2H(n-2) + 2 + 1 .... = 2^(n-1) H(1) + 2^(n-2) + ... + 1 = 2^(n-1) + 2^(n-2) + ... + 1 = 2^n - 1.

而且 honoi 塔的解决方案应该打印 2^n - 1 次移动，这等于你的算法的运行时间，所以你的输出的大小和你的算法的运行时间关系是线性的，事实上

lim _n->∞ output / runtime = constant.

这意味着算法的运行时间与输出呈线性关系(但正如您所见，它与输入的关系是指数关系)。

同样，在再次寻找最大值时，您可以使用这样的 lim 来说明它与输入具有线性关系。