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

Question

数组 a 的长度也是如此n，p 是长度为 2 的数组。p 中的int两个元素都为零。第一个电话是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 次，具体取决于数组的长度。你们有什么感想

标签： javabig-o

Answer 1

好吧，i在第一次调用中是根据定义n-1，即与 相同的数量级n。因此，出于 big-O-over- nnotation 的目的，初始i值可以被视为n。

除了递归调用之外，代码本身是常数时间：没有 fors 或 while 或任何其他方式会影响此代码的执行次数。

递归调用必然会走向结束条件（i == 0，当没有递归发生时），并且在 O(n) 时间内这样做：事实上，在精确的n步骤之后，将达到 0。

因此，我们有一个执行O(i-initial)时间为 O(1) 的“循环”，其中i-initial与 的量级相同n，它结合到O(1) * O(n)是O(n)。

为了帮助您并确认大 O 符号，这里是大 O 的“要点”：

制作二维折线图。在 x 轴上，输入“n”。在 y 轴上，输入“CPU 花费的时间”。

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

对于这个算法，一条直线，即不是水平的。换句话说，看起来y = C*xC 是一些常数。这就是意思：对于某些 C，O(n)该图最终将稳定下来并且看起来确实如此。y = C*x

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