所以呢 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次取决于数组的长度。你们怎么看
2条答案
按热度按时间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)+no(1)
findbigo(n)=o(1)+no(1)
findbigo(n)=o(1)+no(1)
findbigo(n)=o(1)+o(n)
findbigo(n)<=o(n)+o(n)
findbigo(n)<=2*o(n)
o(n)中的findbigo
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
在它的右翼。