(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

Kest

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

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

Многие алгоритмы предлагают выбор между объемом памяти и скоростью.
Задачу можно решить быстро, используя большой объем памяти, или медленнее,
занимая меньший объем.
Типичным примером в данном случае служит алгоритм поиска кратчайшего
пути. Представив карту города в виде сети, можно написать алгоритм для опреде-
ления кратчайшего расстояния между любыми двумя точками в этой сети. Чтобы
не вычислять эти расстояния всякий раз, когда они вам нужны, вы можете вывес-
ти кратчайшие расстояния между всеми точками и сохранить результаты в табли-
це. Когда вам понадобится узнать кратчайшее расстояние между двумя заданны-
ми точками, вы можете взять готовое значение из таблицы.
Результат будет получен практически мгновенно, но это потребует огромного
объема памяти. Карта улиц большого города, такогр как Бостон или Денвер, мо-
жет содержать несколько сотен тысяч точек. Таблица, хранящая всю информацию
о кратчайших расстояниях, должна иметь более 10 млрд ячеек. В этом случае вы-
бор между временем исполнения и объемом требуемой памяти очевиден: исполь-
зуя дополнительные 10 Гб памяти, можно сделать выполнение программы более
быстрым.
Из этой особенной зависимости между временем и памятью проистекает идея
объемо-временной сложности. При таком способе анализа алгоритм оценивается
как с точки зрения скорости, так и с точки зрения используемой памяти. Таким
образом находится компромисс между этими двумя показателями.
В данной книге основное внимание уделяется временной сложности, но также
указываются и некоторые Особые требования к объемам памяти для некоторых
алгоритмов. Например, сортировка слиянием (mergesort), рассматриваемая в гла-
ве 9, требует очень больших объемов оперативной памяти. Для других алгорит-
мов, например пирамидальной сортировки (heapsort), которая также описывается
в главе 9, достаточно обычного объема памяти.

Ссылки по теме


 Распечатать »
 Правила публикации »
  Написать редактору 
 Рекомендовать » Дата публикации: 19.07.2012 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Enterprise Connectors (1 Year term)
Delphi Professional Named User
Allround Automation PL/SQL Developer Single user license
EMS SQL Management Studio for PostgreSQL (Business) + 1 Year Maintenance
Rational ClearCase Multisite Floating User License
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
Реестр Windows. Секреты работы на компьютере
СУБД Oracle "с нуля"
Adobe Photoshop: алхимия дизайна
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
 



    
rambler's top100 Rambler's Top100