algorithm - 最好和最坏的情况

Question

我需要帮助来找到此代码的最佳情况和最坏情况并进行解释。我认为最坏的情况是 O(n)。

public static boolean adjacentDuplicates(int[] a) {
  for (int i = 0; i < a.length-1; i++)
    if (a[i] == a[i+1]) return true;
  return false;
}

标签： algorithm

Answer 1

最好的情况是在第一次比较return值。因此，如果a[0] == a[1]时间复杂度为\Theta(1)。更糟糕的是，直到循环结束，比较才会得到满足。因此，最坏情况的复杂度是\Theta(n)（即n输入数组的长度a）。