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

Question

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

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

(п) раствор

Уплотнительное будет:

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

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

Уплотнительного (п * войти п) решение будет:

1. Удалить первый элемент из массива (e1)
2. Задача представляет собой разность между первым элементом и х
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

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

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

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) раз за поиск в среднем.