3

我在 C++ 中的算法中有以下来自 robert sedwick 的程序

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-1 次方的问题分成两个问题来解决大小为 2 的 n 次方问题。

我理解标尺和最大值，但上述声明中的河内塔怎么样？

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

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

4

1 回答 1

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->∞ 输出 / 运行时间 = 常数。

这意味着算法的运行时间与输出呈线性关系（但您可以看到它与输入的关系是指数的）。

同样在再次找到最大值时，您可以使用这样的 alim来表示它与输入具有线性关系。

于 2012-09-07T18:08:01.757 回答