0
Может ли кто-нибудь объяснить, как описанный ниже подход к данной проблеме работает в O (N) времени и O (1) пространстве?Каким может быть время выполнения следующего подхода: O (N) и сложность пространства O (1)?
Вопрос: Учитывая 2 отсортированных массива, найдите количество элементов в общем. Массивы имеют одинаковую длину, каждая из которых имеет разные элементы.
Возьмите следующие 2 массивов, например:
A: 13, 27, 35, 40, 49, 55, 59
B: 17, 35, 39, 40, 55, 58, 60
- сделать линейный поиск в B для A [0] = 13. Начало в B [0] = 17. Остановка на B [0] = 17. Не найдено
- Выполнение линейного поиска в B для A [1] = 27. Начать с B [0] = 17. Остановить при B [1] = 35. Не найдено
- Выполнение линейного поиска в B для A [2] = 35. Начать с B [1] = 35. Остановить при B [1] = 35. найдено
- Сделайте линейный поиск в B для A [3] = 40. Начните с B [2]= 39. Остановка при B [3] = 40. найдено
- Выполнение линейного поиска в B для A [4] = 49. Начать с B [3] = 40. Остановить при B [4] = 55. найдено
Я запутался в той части, где мы делаем линейную петлю для получения всех элементов для A, составляющих O (N), и затем снова выполняем линейный поиск в B, чтобы найти элемент. Поиск лайнера в B поднимается там, где последний остановился. Разве это не усложнит временной подход данного подхода O (N^2)? Если нет, то почему?
@JimMischel Нет, потому что вы просматриваете только то, с чего вы остановились на предыдущем шаге. В конце процесса вы будете посещать каждый элемент в A и B ровно один раз, это O (n). И размер входных данных никогда не включается в требования к пространству алгоритма. – biziclop
А, я читал это слишком быстро. Да, это просто слияние, заявленное по-другому. O (n), с O (1) дополнительным пространством. –
@JimMischel: Итак, лучший случай O (N) и наихудший случай O (N^2)? – Milin