0

我正在学习算法设计课程，我有一个计算函数成本的作业，我做了一些研究并发现了主定理，但我看到的所有例子都是关于n的，在这个函数中我有 2 个参数，但都没有是 n。

function estudia(i,j){
    if i = j then resulta(i,j);
    M = (i+j)/2;
    C = (j-i)/4;
    estudia(i,M);
    estudia(i+C,M+C);
    combina(i,j);
}

function combina(i,j){
    ancho = j-i-1;
    p = 1;
    while p * p < ancho loop
        p = p+1;
        resulta(p,j);
}

我们知道 resulta(x,y) 是 O(1)，但是我如何计算具有 2 个参数 i 和 j 而不是 n 的主定理的递归函数的成本？是不可能的，我必须使用替换方法？

4

1 回答 1

0

根据您的设置，我们假设 i 和 j 是固定参数。让n = j - i，距离。

为estudia(i,M)，距离M-i=n/2，为estudia(i+C,M+C)，距离还在n/2。combina(i,j)=combina(n).

让T(n)= 学习成本。您可以构造递归公式为estudia：

T(n) = 2 * T(n/2) + combina(n).

正如你所说，你可以解决combina(n)（我不会解决它，因为它仍然是你的任务）。插入结果combina(n)，你得到主定理。

于 2017-02-05T00:31:23.487 回答