具有多次递归的算法的时间复杂度

Question

我想知道以下算法的时间复杂度：

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值的问题。有人可以帮帮我吗？

Answer 1

我不知道你教的是什么技术，但我知道如何从头开始解决这个问题。

划分问题时，将递归调用的成本按比例分配给较低级别​​。然后问一个问题，即最大值可以分配到底部的任何值。

这就是我的意思。

如果你正在寻找一系列长度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)。