Методика преобразования (Определение. Алгоритмы и задачи:схема Горнера вычисления значения полинома в точке, бинарное возведение в степень, пирамидальная сортировка, приведение задач, задача линейного программирования)

Метод преобразования

• Состоит в том, что экземпляр задачи преобразуется в другой, по той или иной причине легче поддающийся решению.

• Имеется три основных варианта этого метода:

Пример 1: проверка единственности элементов массива

• Алгоритм на основе грубой силы попарно сравнивает все элементы, пока не будут найдены два одинаковых либо пока не будут пересмотрены все возможные пары. В наихудшем случае эффективность квадратична.

• К решению задачи можно подойти и по-другому — сначала отсортировать массив, а затем сравнивать только последовательные элементы.

• Время работы алгоритма - сумма времени сортировки и времени на проверку соседних элементов.

• Если воспользоваться хорошим алгоритмом сортировки, весь алгоритм проверки единственности элементов массива также будет иметь эффективность О (n log n)

Пример 2: поиск

• Метод грубой силы: последовательный поиск

• Метод преобразования задачи: сортировка + бинарный поиск

• Требуется оценить наименьшее количество поисков, при котором окупается предварительная сортировка

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.