Наихудший случай Сценарий Время Сложность операции добавления / удаления для ограниченного набора с использованием массивов?

Question

Я пометил это как Java, потому что я выбрал эту цитату из «Коллекции Java» - рекомендуемый текст для курса, который я делаю.

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

Я цитирую книгу, которая предназначена для операции добавления.:

"Этап поиска - O (logn). Этап вставки - O (n), но пропускается, если добавляемое значение уже является членом. Таким образом, операция в целом - O (n) в целом "

Почему общая сложность времени не равна O (nx logn)?

Кроме того, если у вас есть какие-либо другие предлагаемые тексты, которые могут быть проще для неспециалистов, которые вы бы порекомендовали, это было бы очень признательно.

Спасибо.

Answer 1

Поскольку бинарный поиск - это O (logn), а стадия вставки - O (n), технически сложность времени равна O (n + logn).Поскольку logn незначителен по сравнению с n, вы можете просто удалить logn, дающий ответ O (n).