Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 1. Основные понятия

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

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

Анализ скорости выполнения алгоритмов

Теория сложности изучает сложность алгоритмов. Существует несколько спо­собов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели - требо­вания к объему памяти, свободному месту на диске. Использование быстрого ал­горитма не приведет к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у вашего компьютера.

Память или время

Многие алгоритмы предлагают выбор между объемом памяти и скоростью. Задачу можно решить быстро, используя большой объем памяти, или медленнее, занимая меньший объем.

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

Результат будет получен практически мгновенно, но это потребует огромного объема памяти. Карта улиц большого города, такого как Бостон или Денвер, мо­жет содержать несколько сотен тысяч точек. Таблица, хранящая всю информацию о кратчайших расстояниях, должна иметь более 10 млрд ячеек. В этом случае вы­бор между временем исполнения и объемом требуемой памяти очевиден: исполь­зуя дополнительные 10 Гб памяти, можно сделать выполнение программы более быстрым.

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

В данной книге основное внимание уделяется временной сложности, но также указываются и некоторые Особые требования к объемам памяти для некоторых алгоритмов. Например, сортировка слиянием (mergesort), рассматриваемая в гла­ве 9, требует очень больших объемов оперативной памяти. Для других алгорит­мов, например пирамидальной сортировки (heapsort), которая также описывается в главе 9, достаточно обычного объема памяти.

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.