练习递归和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];
}
}
但我不确定运行时是什么。它不是线性的吗?
最佳答案
令算法消耗的时间为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
(输入的大小)成线性关系。
关于java - 在递归算法中计算运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14040778/