具有 2 个参数的主定理，n

Question

我正在上一门算法设计课程，我有一个计算函数成本的家庭作业，我做了一些研究并发现了主定理，但我看到的所有例子都是关于 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 的主定理来计算递归函数的成本？不可能，我必须使用替代方法？

Answer 1

根据您的设置，我们假设 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) 的结果，你得到主定理。

具有 2 个参数的主定理，n

master theorem with 2 parameters, neither n

algorithm

time

master

theorem