вектора, не обращаться
вектора, не обращаться к последней, (N-1)-й, компоненте. Очевидно, алгоритм E3-3 применим в тех случаях, когда постановка задачи не требует "смыкания рядов" после удаления заданного элемента. Трудоемкость O(1) выглядит гораздо симпатичнее, чем линейная, не так ли?
На основе приема фиктивного удаления решается полезная в приложениях задача генерации чисел из заданного отрезка натурального ряда в случайном порядке; сами числа при этом удобно размещать в векторе. Можно, конечно, после генерации очередного числа проверить ранее размещенные и, обнаружив совпадение, игнорировать очередное значение, но тогда многократные повторения просмотра приведут к трудоемкости O(N2), не говоря уж о том, что и датчик случайных чисел вполне способен растянуть этот процесс во времени.
Нет сомнений, что линейная эффективность нас больше устроит. Удобно будет продемонстрировать алгоритм для интервала 1..N, а читателю рекомендуем сравнить его с алгоритмом E1-1.
Алгоритм E3-4
*
ячейки вектора
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
