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

Question

练习递归和D&C，一个常见的问题似乎是转换数组:
[a1,a2,a3..an,b1,b2,b3...bn] 到 [a1,b1,a2,b2,a3,b3...an,bn]
我按如下方式解决了它(startA 是 a 的开始，startB 是 b 的开始:

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

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

Answer 1

令算法消耗的时间为T(n)，令n=startB-startA。

每次递归调用将运行时间减 1(startB-startA 每次调用减一)，因此运行时间为 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(输入的大小)成线性关系。