Блог

Возникли проблемы с поиском временной сложности для наихудшей временной сложности. Этот случай относится к пересечению двух массивов сортировки одинакового размера (n).

Не уверен, как подсчитать цикл while с двумя условиями или как подсчитать операторы if и else if

Я знаю, что большим 0 будет N N, но не знаю, как показать наихудший случай.

 int printIntersection(int arr1[], int arr2[])  {
  int i = 0, j = 0;
  while (i < n amp;amp; 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  ;
    }
  }
}
 

Чтобы доказать, что в наихудшем случае цикл выполнит 2N итераций, вы можете использовать следующий аргумент.
Учитывая два индекса i и j на каждом шаге:

• если arr1[i] < arr2[j] тогда i увеличивается на 1
• если arr2[i] > arr1[j] тогда j увеличивается на 1
• если arr2[i] = arr1[j] тогда оба i и j увеличиваются на 1

На каждой итерации по крайней мере одна между i и j увеличивается на единицу, а максимальное количество итераций ограничено 2N (как i, так и j идут от 0 до n-1), вы получаете результирующую временную сложность в наихудшем случае.