VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования — страница 15

  • Просмотров 28022
  • Скачиваний 535
  • Размер файла 384
    Кб

система, то алгоритм открывания двери может быть достаточно сложным. Формализацией алгоритмов занимаются уже тысячи лет. За 300 лет до н.э. Евклид написал алгоритмы деления углов пополам, проверки равенства треугольников и решения других геометрических задач. Он начал с небольшого словаря аксиом, таких как «параллельные линии не пересекаются» и построил на их основе алгоритмы для решения сложных задач. Формализованные

алгоритмы такого типа хорошо подходят для задач математики, где должна быть доказана истинность какого‑либо положения или возможность выполнения каких‑то действий, скорость же исполнения алгоритма не важна. Для выполнения реальных задач, связанных с выполнением инструкций, например задачи сортировки на компьютере записей о миллионе покупателей, эффективность выполнения становится важной частью постановки задачи.

Анализ скорости выполнения алгоритмов Есть несколько способов оценки сложности алгоритмов. Программисты обычно сосредотачивают внимание на скорости алгоритма, но важны и другие требования, например, к размеру памяти, свободному месту на диске или другим ресурсам. От быстрого алгоритма может быть мало толку, если под него требуется больше памяти, чем установлено на компьютере. Пространство — время [RP1]  Многие алгоритмы

предоставляют выбор между скоростью выполнения и используемыми программой ресурсами. Задача может выполняться быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший объем памяти. ===========2 Хорошим примером в данном случае может служить алгоритм нахождения кратчайшего пути. Задав карту улиц города в виде сети, можно написать алгоритм, вычисляющий кратчайшее расстояние между любыми двумя точками в этой сети.

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

города, такого как Бостон или Денвер, может содержать сотни тысяч точек. Для такой сети таблица кратчайших расстояний содержала бы более 10 миллиардов записей. В этом случае выбор между временем исполнения и объемом требуемой памяти очевиден: поставив дополнительные 10 гигабайт оперативной памяти, можно заставить программу выполняться гораздо быстрее. Из этой связи вытекает идея пространственно‑временной сложности