В программирование алгоритмов. Оценка алгоритмов с точки зрения времени и объёма. Схема Горнера для вычисления значений многочленов

Введение в программирование алгоритмов

Создание вычислительных машин было необходимым шагом технического прогресса в связи с появлением широкого класса задач требующих большой объем вычислений. Создание вычислительных машин в свою очередь выдвинула проблему составления определенных инструкций для управления работой вычислительных машин. Таким образом, появилась необходимость проектирования алгоритмов для ВМ (вычислительных машин) и составления программ в соответствии с этими алгоритмами. Несмотря на большое быстродействие современных компьютеров существуют и появляются все новые задачи, требующие такого объема вычисления, что не под силу даже современным ВМ. В ходе изложения мы ещё не раз обратим внимание на класс таких задач.

Введение в программирование алгоритмов

Мы здесь приведем одну хорошо известную среди специалистов задачу, связанную с шахматами: определить маршрут проходящий по правилу хода конём от клетки А1 и приходя по всем клеткам шахматной доски только по одному разу и возвращающуюся в исходную клетку А1. Если изложить данную задачу в терминах теории графов, то получим Гамильтонов граф, вершины которого расположены на клетках шахматной доски, а ребра графа - это линии соединяющие те клетки, по которым движется шахматная фигура при совершении хода конем.

Введение в программирование алгоритмов

При этом число возможных вариантов маршрутов исчисляется по формуле N        2 3 4 6 8 28 10 . 4 8 20 16 16 21 Как видно, даже в этой на вид простой задаче мы сталкиваемся с таким огромным количеством вариантов. Если в таком графе каждое ребро имеет определенную цену перехода и нам необходимо из всех возможных маршрутов выбрать наименьший по цене маршрут, то такая задача не под силу даже современным быстродействующим ВМ. Вместе с тем для сравнения мы должны хранить информацию о каждом маршруте, для чего потребуется такой объем памяти, для которого не хватит объема памяти ВМ.

Оценка алгоритмов с точки зрения времени и обьёма

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём. Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.