-1

我试图找到每一行的运行时间，最好的情况和最坏的情况会发生，以及 Big-O 在最坏和最好的情况下。

我粘贴的代码所做的是找到数组中升序数字序列的最长长度。

例如，如果我们有 [4,5,6,9,1,2,3,4,5,6] ，最长的序列将是 6。

第一个 for 循环会被执行 n 次吗？
第二个for循环会执行n次吗？
if语句会被执行n次吗？
if中的语句会被执行n次吗？

当数组按升序排列时会出现最好的情况，而当数组按降序排列时会出现最坏的情况吗？


我不相信这是真的的原因是，当它按升序排序时，第二个循环将一直运行。当它按降序排序时，第二个循环总是会中断，因为 and 语句不成立。

for (i = 0, length = 1; i < n-1; i++) {
  for (i1 = i2 = k = i; k < n-1 && a[k] < a[k+1]; k++, i2++);
  if (length < i2 - i1 + 1)
    length = i2 - i1 + 1;
}
return length;
4

1 回答 1

0

首先，注意变量i1和i2并不是真正需要的，因为i1 == i和i2 == k在内循环的每次迭代中，所以我们可以写：

for (i = 0, length = 1; i < n-1; i++) {
  for (k = i; k < n-1 && a[k] < a[k+1]; k++);
  if (length < k - i + 1)
    length = k - i + 1;
}
return length;

外部循环将执行 n-1 次。在最坏/最好的情况下没有区别。

最好的情况发生在a非递增序列时。在那种情况下a[k] < a[k+1]永远不会是真的，因此内部循环的条件只会被执行一次。在这种情况下，返回值为 1，时间复杂度为O(n)。

最坏的情况发生在a不断增加的序列时。在那种情况下a[k] < a[k+1]将始终为真，因此内部循环的条件将迭代n-1 - ik < n-1次，当为假时，循环的条件将再一次。

在恒定时间内执行的if条件和调整。length

嵌套循环的主体 (the if) 总共执行的次数与可以从一组n-1 个元素中生成 2 个元素的多重集（由i和表示）一样多。其公式为 (n-1)n/2，即O(n²)。k

于 2019-10-05T20:06:27.563 回答