Java 中以下最小和最大递归代码的大 O 表示法

Question

所以 n 是数组 a 的长度，p 是 int 个 len 2.both 元素的数组 p 中的元素为零。第一次调用是 findbigO(a, n-1, p).

findbigO(int[] a, int i, int[] p)
if (i == 0) {
   p[0] = a[0];
   p[1] = a[0];
} else {
   findbigO(a, i‐1, p);
   if (a[i] < p[0]]) {
      p[0] = a[i];
   }
   if (a[i] > p[1]]) {
      p[1] = a[i];
   }
}

代码基本上是在一个数组中找到最大值和最小值，并将它们存储在不同的数组 P 中。我试图找出这段代码的大 O。我认为它是 n 的大 O，因为递归根据数组的长度被调用 n 次。大家怎么看

Answer 1

好吧，根据定义，第一次调用中的 i 是 n-1，即与 n 大小相同。因此，对于 big-O-over-n 表示法，初始 i 可以被视为 n.

除了递归调用之外，代码本身是恒定时间：此代码的执行次数不会受到任何影响。

递归调用必然会向结束条件前进（i == 0，当没有递归发生时），并且在 O(n) 时间内完成：事实上，恰好在 n 步之后，0 将已达到。

因此，我们有一个 O(1) 'loop' 被执行 O(i-initial) 次，其中 i-initial 与 n 的大小相同，合并为 O(1) * O(n) 就是 O(n).

为了帮助您确认大 O 符号，这里是大 O 的 'point'：

制作二维线图。在 x 轴上，输入 'n'。在 y 轴上，输入 'time taken by the CPU'.

然后填写这张图表。起初它会很混乱（也许在其中一个运行中，您的 winamp 切换歌曲或诸如此类），但是向右走得足够远，输入的算法复杂性将开始成为决定因素。它'balances out'，换句话说，变成了一个可识别的图形。该图是什么样的？

对于这个算法，一条直线，不是水平的。换句话说，它看起来像 y = C*x，其中 C 是某个常数。这就是 O(n) 的意思：该图最终会稳定下来，看起来像 y = C*x 那样，对于某些 C.

O(n^2) 表示：图形最终稳定为看起来像 y = x^2 的东西。这也是为什么 O(x^2 + x) 不是一个东西，因为 y = x^2 + x，一旦你向右走得足够远，看起来就像 y = x^2 在它的右侧。

Answer 2

findbigO(n) = findbigO(n-1) + (1)

findbigO(n) = (findbigO(n-2) + O(1)) + (1)

...

findbigO(n) = findbigO(n-n) + n*O(1)

findbigO(n) = findbigO(0) + n*O(1)

findbigO(n) = O(1) + n*O(1)

findbigO(n) = O(1) + O(n)

findbigO(n) <= O(n) + O(n)

findbigO(n) <= 2*O(n)

O(n) 中的 findbigO

Java 中以下最小和最大递归代码的大 O 表示法

Big O notation of the following min and max recursive code in Java

java

big-o