» » »

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

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

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

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



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

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

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

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

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

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

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

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

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




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