我们如何从给定的代码编写递归公式

Question

f(A, i, j) {
    print("f", i, j);
    n := j-i+1;
    mid := floor((i+j)/2);
    if (n>1) {
        f(A, i, mid);
        f(A, mid+1, j);
        g(A, i, j);
    }
}


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）代表时间吗？我知道答案是T（n）= 3T（n / 2）+ O（n），但是为什么T（n / 2）是从哪里来的，有人可以详细解释它的答案吗得出T（n）= 3T（n / 2）+ O（n）的结论。谢谢

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循环。

一旦发生类似这样的重复，您可以使用master theorem将T（n）的递归定义转换为T（n）行为的直接界限。在这里，运行时可以完成

T（n）= O（n ^{log ₂ 3}），

我们通过查看主定理的情况获得的结果，看看哪个适用。