确定给定算法的递归关系

Question

void function(int A[], int i, int j){
    if (j == i+1) 
        if (A[i] > A[j])
            swap(A,i,j)
        else {
            int k = (j-i+1)/3;
            function(A,i,j-k); 
            function(A,i+k,j);
            function(A,i,j-k); 
        }
}

这段代码摘自我算法分析class中的一次期中考试。要求学生推导出描述此函数行为的递归关系。我在 Internet 上看到了一些关于如何完成此过程的示例，但我就是想不通如何将其应用于此特定功能，i 和 j 索引让我感到很困惑。

有什么想法吗？

Answer 1

每个[i,j-k],[i+k,j],[i,j-k]都是[i,j]的2/3。因此，当每个部分都是原始大小的三分之二时，您将问题划分为 3 个部分。因此你的递归关系是T(n) = 3*T(n*2/3)。您可以使用大师定理解决这个问题。

确定给定算法的递归关系

Determining a recurrence relation for a given algorithm

algorithm

recurrence