java - 递归算法中的运行时间计算

练习递归和D&C，一个常见的问题似乎是转换数组：
[a1,a2,a3..an,b1,b2,b3...bn]到[a1,b1,a2,b2,a3,b3...an,bn]
我的解是这样的（startA是as的开始，startB是bs的开始：

private static void shuffle(int[] a, int startA, int startB){
        if(startA == startB)return;
        int tmp = a[startB];
        shift(a, startA + 1, startB);
        a[startA + 1] = tmp;
        shuffle(a, startA + 2, startB + 1);
    }

    private static void shift(int[] a, int start, int end) {
        if(start >= end)return;
        for(int i = end; i > start; i--){
            a[i] = a[i - 1];
        }
    }

但我不确定运行时是什么。不是线性的吗？

最佳答案

让算法消耗的时间T(n)，并让n=startB-startA。
每次递归调用都会将运行时间减少1（startB-startA每次调用会减少1），因此运行时间是T(n) = T(n-1) + f(n)，我们只需要知道f(n)是什么。
每次调用的瓶颈是shift()操作，它从startA+1迭代到startB，这意味着n-1迭代。
因此，该算法的复杂性为T(n) = T(n-1) + (n-1)。
但是，这是一个已知的Theta(n^2)函数（sum of arithmetic progression）-并且算法的时间复杂度是Theta(N^2)，因为初始startB-startA与N（输入的大小）是线性的。