Вычисление O(n) для hasmap против двоичного поиска

Question

Я пытаюсь уточнить, как рассчитать O (n) для следующего случая:

Учитывая отсортированный массив, как бы вы нашли два числа, сумма которых равна заданному числу x в O (n)?

Решение O (n) будет:

1. Удалить первый элемент массива (e0)
2. Добавьте это к хэш-карте
3. Удалить первый элемент массива (e1)
4. Цель - это разница между е1 и х
5. Если цель существует в хэш-карте, верните пару
6. Добавьте e1 к хэш-карте
7. Повторяйте шаги 3-6, пока не найдете пару или не закончились элементы

Это будет наихудший случай O (n), так как вам нужен только один проход в массиве.

Решение O(n * log n) будет:

1. Удалить первый элемент из массива (e1)
2. Цель - это разница между первым элементом и x
3. Двоичный поиск остальной части массива для цели
4. Если он существует, верните пару
5. Повторите шаги 1–4, пока не найдете пару или не закончились элементы

Это O (n log n), так как вам нужно будет выполнить бинарный поиск (log n) в худшем случае n/2 раза, давая O(n/2 * log n), что в большом O равно O(n * log n)

Это правильно?

Answer 1

Да, для обоих алгоритмов ваш анализ является правильным.

Ваш первый алгоритм использует также O(n) пространство, потому что hashmap. Вы можете избежать этого.

Algo : 
1. Consider begin = 0, and end = last_index
2. Consider data[begin] and data[end]
3. If data[begin] + data[end] > req_sum:
        end=end - 1  // u need to decrease ur total sum
   elif data[begin] + data[end] < req_sum:
        begin = begin + 1  // u need to increase ur total sum
   elif data[begin] + data[end] == req_sum:
          print("found")
4. Continue from Step 2.

Очевидно избегать случая, когда end < begin и другие угловые случаи.

Answer 2

Это звучит как проблема с домашним заданием в каком-то курсе, который вы принимаете. Я не буду решать это за вас - хотя найти решение в Интернете достаточно просто, - но я скажу вам, что я на 99% уверен, что ваше решение должно занять O(n) времени как наихудшая сложность. Решения на основе хеша в среднем занимают всего O(1) раз за поиск.