为这个递归函数找一个递归关系？

Question

考虑以下函数。

g(A, i, j) {
    print("g", i, j);
    n := j-i+1;
    if (n == 2) {
        if (A[i] > A[j]) swap A[i] and A[j];
    }
    else {
        for(k := 0 to n/4-1) swap A[i+n/4+k] with A[i+n/2+k];

        // swap 2nd and 3rd quarters
        g(A, i, i+n/2-1); // recurse on 1st and 2nd quarters
        g(A, i+n/2, j); // recurse on 3rd and 4th quarters
        g(A, i+n/4, i+3n/4-1); // recurse on 2nd and 3rd quarters
    }
}

我将如何推导出函数g的运行时间的递归关系？我看到的答案是

T(n)=3T(n 2)+O(n)。

在这个表达式中，T(n)是指 "时间 "吗？这里的n 2是怎么来的？而且，更一般地，我如何找到这样的递归？

Answer 1

你可以阅读递归

T(n) = 3T(n 2) + O(n)

作为定义一些函数T(n)，决定了该函数需要多少时间。g 在一个总共包含n个元素的数组上运行。因为函数 g 是递归的，T(n)的定义也是递归的。

在这里，3T(n 2)的意思是 "有三个递归调用，每个递归调用都是对一个大小为n 2的子问题进行的"。要知道这是为什么，请注意，在递归的情况下。g 对自己的范围进行三次呼叫

g(A, i, i+n/2-1); // recurse on 1st and 2nd quarters
g(A, i+n/2, j); // recurse on 3rd and 4th quarters
g(A, i+n/4, i+3n/4-1); // recurse on 2nd and 3rd quarters

每个范围内的元素总数是n 2(你明白为什么了吗？)，因此有3T(n 2)位。

之所以有 "+ O(n)"，是因为算法在递归的情况下，独立于进行递归调用的工作，做的是线性的工作量。这是从 for 循环上面的递归调用。

一旦你有了一个像这样的递归，你就可以使用 主定理 以将 T(n) 的递归定义转换为 T(n) 行为方式的直接约束。在这里，运行时间的计算结果是

T(n)=O(n)^{原木₂ 3}),

我们通过观察主定理的情况来获得，看看哪一个适用。