algorithm - 确定给定算法的递归关系

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); 
        }
}

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

有什么想法吗？

Answer 1

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