3

这是我的算法课上的一个老作业问题。我有解决问题的办法，但即使经过多次尝试，我也无法理解如何朝着正确的方向思考以得出解决方案。

function h(N) {
    if (N==1) return 3;
    else { 
        sum = 1;
        i = 0;
        while (i < h(N-1))
            sum = sum + i;
            i = i + 1;
        return sum;
   }
}

据我说，由于 h(N-1) 在 while 循环中被重复调用，所以 while 循环应该运行与 h(N-1) 返回的次数一样多的次数。除此之外，while 循环中的函数调用 h(N-1) 也会发生很多次。因此，根据我的说法，我应该得到这样的东西：

T(N) = T(N-1)*H(N-1) + C*H(N-1) + D

其中
1. T(N) 是运行时间，
2. T(N-1)*H(N-1) 因为对 h(N-1) 的一次递归调用将占用 T(N-1) 并且因为它是每次进行比较时重新计算，它将被称为 H(N-1) 次。（其中 H(N-1) 是调用返回的值）
3. C*H(N-1) 是 while 循环内语句的运行时间（因为 while 循环运行 H(N-1)次。

我没有从教授那里得到满意的答案，如果有人能帮助我理解这一点，我将不胜感激。

谢谢！

4

2 回答 2

2

尝试分两步理解这一点，首先考虑这个更简单的函数，我们将while循环替换为if.

function g(N) {
    if (N==1) return 3;
    else { 
        sum = 1;
        i = 0;
        if(i < g(N-1))
            sum = sum + i;
            i = i + 1;
        return sum;
   }
}

在这里，我们得到递归：

G(N) = G(N-1) + O(1)

到现在为止还挺好？在这里，计算 g(N) 的工作涉及解决较小的问题 g(N-1) 加上恒定的工作量。

现在，让我们回到原来的函数 h(N)。发生了什么变化？现在，计算 h(N) 的工作涉及求解子问题 h(N-1), h(N-1) 次。并且在每一次（即在while 循环中），我们都会做大量的工作。还有另一个恒定量的工作在 h(N) 中只完成一次，即在 while 循环之外。所以，我们基本上得到：

H(N) = H(N - 1) *{H(N - 1) + O(1)}  + O(1)

我们可以通过替换来重写上面的内容T(n) = H(n) + O(1)。因此，我们得到：

T(N) = H(N - 1) * T(N - 1)  + O(1)
于 2012-05-13T11:46:08.183 回答
1

假设在执行 h(N) 时，在循环的每次迭代中都会重新计算 h(N-1) 的值（这可能是大多数语言和大多数编译器的情况）

在此处输入图像描述

于 2012-05-12T08:45:43.637 回答