Для сортировки вставки требуется вставить элемент в отсортированном порядке на с изменением элементов уже отсортированного списка при использовании через массив. Если вместо использования массивов мы используем дважды связанный список, , какова будет временная сложность?сложность сортировки вставки с использованием двусвязного списка?
Сложность времени Представляет собой O (n^2)? Зачем? Если мы рассмотрим вставку для n элементов, то это будет log (1) + log (2) + log (3) + ..... + log (n) - n раз для n элементов , следовательно, сложность должна быть O (NlogN)
Что заставляет вас думать, что это «log (1) + log (2) + ... + log (n)', а не '1 + 2 + ... + n'? Пожалуйста, добавьте более подробную информацию в вопросы, так что вы получите более подробные ответы - что будет более вероятно объяснить, где ваша ошибка. – amit
для вставки с использованием сортировки вставки, если мы используем дважды связанный список, тогда вставка элемента принимает log (k) время, где k - количество уже отсортированных элементов – Luv