Skiena, в Руководстве по проектированию алгоритмов, указывает, что вставка в отсортированный массив O (n). Однако поиск элемента в отсортированном массиве - O (log n), потому что вы можете выполнить двоичный поиск.Почему вставка в отсортированный массив O (n)?
Невозможно вставить также O (log n), если бы я выполнил бинарные сравнения поиска, чтобы выяснить, в каком массиве он должен идти?
Нахождение позиции - это только половина сражения. Покажите мне, как разместить 2 на своем месте в [1,3,4,5,6,7], используя менее пяти операций перемещения.
Вы можете выполнять поиск O (log n) в отсортированном массиве, но когда вы вставляете элемент, который вам нужно переместить, так что сдвиг O (n).
Вы можете использовать бинарный поиск, чтобы выяснить, куда должен идти элемент. Однако вставка элемента означает, что вам нужно освободить место для него. Это делается путем перемещения всех элементов после нового элемента вправо. Это требует сложности O (n).