java中下列min和max递归代码的big o表示法

j7dteeu8  于 2021-07-08  发布在  Java
关注(0)|答案(2)|浏览(266)

所以呢 n 是数组a的长度,p是 int 两个元素在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次取决于数组的长度。你们怎么看

w8rqjzmb

w8rqjzmb1#

findbigo(n)=findbigo(n-1)+(1)
findbigo(n)=(findbigo(n-2)+o(1))+(1)
...
findbigo(n)=findbigo(n-n)+no(1)
findbigo(n)=findbigo(0)+n
o(1)
findbigo(n)=o(1)+no(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

k0pti3hp

k0pti3hp2#

好, i 在第一次通话中 n-1 ,即与 n . 因此,对于大o-over- n 表示法,首字母 i 可以视为 n .
除了递归调用之外,代码本身是恒定时间的:代码的执行不受任何因素的影响。
递归调用必须向结束条件前进(i==0,当没有递归发生时),并且在o(n)时间内这样做:实际上,在 n 步骤,将达到0。
因此,我们有一个o(1)“循环”正在执行 O(i-initial) 时间,地点 i-initial 大小与 n ,它结合到 O(1) * O(n) 这只是 O(n) .
为了帮助您并确认big-o表示法,这里是big-o的“要点”:
做一个二维线图。在x轴上,输入“n”。在y轴上,输入“cpu占用的时间”。
那就填这张表。一开始会很混乱(可能在一次运行中,你的winamp会切换歌曲或者其他什么),但是如果走得足够远,输入的算法复杂性将开始成为决定因素。换句话说,它“平衡”成一个可识别的图形。那张图是什么样子的?
对于这个算法,一条直线,即不是水平的。换句话说,看起来 y = C*x c是常数。那是什么 O(n) 意思是:这个图最终会稳定下来 y = C*x 是的,对某些人来说。 O(n^2) 意思是:图形最终稳定为 y = x^2 . 这也是为什么 O(x^2 + x) 不是一件事,因为 y = x^2 + x ,一旦你走到足够远的右边,看起来就像 y = x^2 在它的右翼。

相关问题