анализировать сложность времени

Question

У меня есть 2 массива

a of length n
b of length m

Теперь я хочу найти все элементы, общие для обоих массивов

Алгоритм

Построить хэш-карту, состоящую из всех элементов A

Теперь для каждого элемента x в B проверьте, присутствует ли элемент x в hashmap.

Анализ общей сложности времени

• для построения хэш-карты O (n)
• для второго шага сложности составляет O (м)

Таким образом, в целом O (m + n). Я прав?

Что такое O (m + n) = ?? когда м большое или наоборот?

Answer 1

O (m) + O (n) = O (m + n), если вы знаете, что m> n, тогда O (m + n) = O (m + m) = O (m).

Примечание: хеши теоретически не гарантируют поиск O (1), но практически вы можете рассчитывать на него (= это средняя сложность, ожидаемое время выполнения для случайного ввода).

Также обратите внимание, что ваш алгоритм будет неоднократно сигнализировать о дублированных элементах b, которые также присутствуют в a. Если это проблема, вы должны сохранить ее в хэше, который вы уже проверили / распечатали.

Answer 2

Средний случай сложность времени O(m + n). Это то, что вы должны учитывать, если вы делаете какую-то реализацию, поскольку хэш-карты обычно не имеют коллизий. O(m+n) = O(max(m, n))

Однако, если это контрольный вопрос, под временной сложностью люди понимают наихудший случай временная сложность. В худшем случае сложность времени составляет O(mn), поскольку каждый из вторых шагов может занять O(n) время в худшем случае.