Какое количество алгоритмов пересечения максимальных сравнений может выполнить?

Question

Итак, у меня есть этот алгоритм ниже, который находит общие элементы в двух SORTED массивах.Учитывая, что оба массива имеют длину m и n соответственно, мне нужно найти максимальное количество сравнений, которые этот алгоритм выполнит.

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

Я думаю, что сложность этого алгоритма составляет O (m + n).Поправьте меня если я ошибаюсь.Итак, будет ли максимальное количество сравнений m + n или m * n?Или ни один из них?

Answer 1

Худший случай был бы, если n> m, первые (m - 1) элементы равны, а последний элемент arr1[m - 1] больше, чем все остальные элементы arr2.Тогда первый if всегда будет неуспешным, код должен будет пройти через все элементы arr2, что приведет к (2 * n) сравнениям.

Но обозначение Big O не указывает точное числоопераций, а точнее темпы его роста .В этих терминах этот алгоритм все еще линейен относительно длины всего ввода, и это записывается как O (n).