所以呢 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*xc是常数。那是什么O(n)意思是：这个图最终会稳定下来y = C*x是的，对某些人来说。O(n^2)意思是：图形最终稳定为y = x^2. 这也是为什么O(x^2 + x)不是一件事，因为y = x^2 + x，一旦你走到足够远的右边，看起来就像y = x^2在它的右翼。