java - 时间和空间的复杂性

Question

我是论坛新手，所以我希望我做得对。

我正在努力弄清楚 bigO 的复杂性。具体来说就是时间复杂度。我现在正在开发一个递归程序，每次递归都会调用自身两次。示例:

compute(i,j)

edge checks

x = (compute(i-1, j) + compute(i, j-1)) /2;

return x;

我认为这是O(2^n)时间，因为每次调用都会产生另外两个。它是否正确？复杂度相同吗？

Answer 1

我建议您使用 int 或 var-args 数组，例如compute(int...val)为第一个操作发送 4 个参数 2，为您在此方法中执行的第二个操作发送最后 2 个参数。

从该方法返回两个操作的加法。

这样你就会得到 O(n) 时间。