time-complexity - 交叉路口的时间复杂度（最坏情况）

Question

难以找到最坏情况时间复杂度的时间复杂度。这种情况适用于两个相同大小 (n) 的排序数组的交集。

不确定如何计算带有两个条件的 while 循环或如何计算 if 和 else if 语句

我知道大 0 将是 N+N 但不知道如何显示最坏的情况。

int printIntersection(int arr1[], int arr2[])  {
  int i = 0, j = 0;
  while (i < n && j < n) {
    if (arr1[i] < arr2[j])
      i++;
    else if (arr2[j] < arr1[i])
      j++;
    else /* if arr1[i] == arr2[j] */ {
      cout << arr2[j] << " ";
      i++;
      j++;
    }
  }
}

标签： time-complexity

Answer 1

为了证明在最坏的情况下循环将进行 2N 次迭代，您可以使用以下参数。
给定两个索引i，j在每一步：

• 如果arr1[i] < arr2[j]theni增加 1
• 如果arr2[i] > arr1[j]thenj增加 1
• if arr2[i] = arr1[j]theni和j都加 1

在每次迭代中，至少i 和 j 之间的一个递增 1，并且最大迭代次数以 2N 为界（i 和 j 都从 0 变为 n-1），您将得到最坏情况下的时间复杂度。