如何为此算法编写递归方程

Question

我对为下面的算法编写递归方程感到困惑，谁能帮我做到这一点？

这是算法：

ThreeSort(A{i..j]){
    n = j-i+1; // number of elements
    if (n==1) return;
    if (n==2) and (A[i] > A[j]) then swap A[i] with A[j]
    else if (n > 2) {
        third = round(n/3);
        ThreeSort(A[i..j-third]); // sort first 2/3rds
        ThreeSort(A[i+third..j]); // sort last 2/3rds
        ThreeSort(A[i..j-third]); // sort first 2/3rds
    }
}

Answer 1

这不是答案，但太长，无法放入评论区，所以我在这里发布。

如果四舍五入，你的代码是错误的round()。假设 n==5 和数组包含6,5,3,2,1项。然后你得到third==2(因为 5/3 = 1.666... 四舍五入(，然后三个步骤的子排序将数组重新排序为：

3,5,6,2,1
3,5,1,2,6 1,3,5,2,6

您需要中间(重叠(部分的长度至少与两侧部分相等，因此您的third不得超过n/3才能正确完成排序。这意味着您需要trunc而不是round。

Answer 2

您必须将数组分为三部分。第一部分是A[i...i+third-1]，第二部分是A[i+third...i+2*third-1]，第三部分是A[i+2*third...j]。排序后

ThreeSort(A[i...i+third-1]);
ThreeSort(A[i+third...i+2*third-1]);
ThreeSort(A[i+2*third...j]);

您必须将数组的三个部分合并为一个。三重合并看起来像二进制合并。

Answer 3

我不确定，但我认为确定时间复杂度的递归方程是T(n(=3*T(n/3(+θ(1(并根据主方法：T(n(∈ θ(n(