Условие задачи
Выбрать эффективный алгоритм вычислительной задачи из двух предложенных, используя теоретическую и практическую оценку вычислительной сложности каждого из алгоритмов, а также его ёмкостную сложность.
Пусть имеется вычислительная задача: дан массив х из n элементов целого типа; удалить из этого массива все значения равные заданному (ключевому) key. Удаление состоит в уменьшении размера массива с сохранением порядка следования всех элементов, как до, так и следующих после удаляемого.
В алгоритме №1 происходит просмотр всех элементов массива начиная с начального элемента с индексом равным ноль. На каждой итерации происходит сравнение значения текущего элемента массива с искомым элементом. Если значение текущего элемента массива совпадает с искомым элементом, то значение текущего элемента заменяется значением последующего элемента, последующий элемент заменяется стоящим за ним и т.д. до конца массива. Таким образом происходит сдвиг части массива «справа» от текущего элемента на место текущего элемента.
В алгоритме №2 вводится специальный указатель (j), который указывает на последнюю ячейку «нового» формируемого массива. Новый массив формируется путём смещения проверяемой ячеек массива в ячейку, на которую указывает специальный указатель. Сначала проверяемая ячейка массива помещается в последнюю ячейку «нового» массива, затем идёт сравнение значения образованной ячейки «нового» массива с ключевым значением. Если при сравнении указатель указывает на ячейку массива с искомым элементом, то при переходе к следующей проверяемой ячейки указатель не изменяется, а в противном случае смещается на следующую ячейку. Таким образом «новый» массив будет находится в начале старого но без ячеек содержащих искомое значение.
Ответ
