时间戳

首页 > 解决方案 > 多重递归算法的时间复杂度

algorithm - 多重递归算法的时间复杂度

问题描述

我正在尝试了解以下算法的时间复杂度：

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 的值。任何人都可以帮助我吗？

标签： algorithmrecursiontime-complexity

解决方案

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

当您划分问题时，将递归调用的成本按比例分配到较低级别。然后询问可以分配给底部任何值的最大值是多少。

这就是我的意思。

如果您正在查看长度范围，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).

推荐阅读