我正在尝试了解以下算法的已知时间复杂度:
static int g(int[] a) {
return g(a, 0, a.length-1);
}
static int g(int[] a, int i, int j) {
if(i == j) return a[i];
int onefourth = (j+1-i)/4;
return g(a, i, i+onefourth) + g(a, i+onefourth+1, j);
}
这是我的尝试:
算法g(int[] a, int i, int j) 将数组a的维度分成4，并通过多次递归递归调用自身。我可以写出以下递归方程 T(n) = T(n/4) + T(3n/4) + c = .... = T(n/4^k) + T(3n/4^k) + kc。在这里，我无法选择 k 值。任何人都可以帮助我吗？
最佳答案
我不知道你学到了什么技术，但我知道我如何从头开始解决这个问题。
当您划分问题时，将递归调用的成本按其大小按比例分配给较低级别。然后问可以分配给底部任何值的最大值是多少。
这就是我的意思。
如果您正在查看长度范围1，您将有一些不变的成本c。
如果您正在查看长度范围 2，您将有一个恒定的递归成本 r 平均划分为 c+ 的每个元素的成本r/2.
如果您查看长度范围 3，第一个元素的成本为 c + r/3 但后一对首先获得 2/3 r 在顶层，然后将其分成 2 和另一个递归成本，总成本为 c + r/2 + r/3。
等等。
挑战来了。可归因于特定调用的最大递归成本是多少？链中某处的最坏情况是其级别为 r，其上方级别为 3/4 r，加上 (3/4)^2 r 用于高于该级别的级别，依此类推。你能找到上限吗？
您能否将该上限转换为归因于底部单个元素的成本的上限？
将它乘以元素的数量，您将得到 O(n)。
关于algorithm - 多次递归算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52313719/