|
Навигация
|
Главная » Новости Анализ скорости выполнения алгоритмовИсточник: codingrusru/readarticlephp?article_id=1449 Kest Теория сложности изучает сложность алгоритмов. Существует несколько спо-собов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели - требо- вания к объему памяти, свободному месту на диске. Использование быстрого ал- горитма не приведет к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у вашего компьютера. Память или время Многие алгоритмы предлагают выбор между объемом памяти и скоростью. Задачу можно решить быстро, используя большой объем памяти, или медленнее, занимая меньший объем. Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для опреде- ления кратчайшего расстояния между любыми двумя точками в этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они вам нужны, вы можете вывес- ти кратчайшие расстояния между всеми точками и сохранить результаты в табли- це. Когда вам понадобится узнать кратчайшее расстояние между двумя заданны- ми точками, вы можете взять готовое значение из таблицы. Результат будет получен практически мгновенно, но это потребует огромного объема памяти. Карта улиц большого города, такогр как Бостон или Денвер, мо- жет содержать несколько сотен тысяч точек. Таблица, хранящая всю информацию о кратчайших расстояниях, должна иметь более 10 млрд ячеек. В этом случае вы- бор между временем исполнения и объемом требуемой памяти очевиден: исполь- зуя дополнительные 10 Гб памяти, можно сделать выполнение программы более быстрым. Из этой особенной зависимости между временем и памятью проистекает идея объемо-временной сложности. При таком способе анализа алгоритм оценивается как с точки зрения скорости, так и с точки зрения используемой памяти. Таким образом находится компромисс между этими двумя показателями. В данной книге основное внимание уделяется временной сложности, но также указываются и некоторые Особые требования к объемам памяти для некоторых алгоритмов. Например, сортировка слиянием (mergesort), рассматриваемая в гла- ве 9, требует очень больших объемов оперативной памяти. Для других алгорит- мов, например пирамидальной сортировки (heapsort), которая также описывается в главе 9, достаточно обычного объема памяти. За что HTML-верстальщики так не любят веб-дизайнеров. Answers Anywhere.. ESET: Обзор информационных угроз марта 2013 года. Все о дизайне. Логотип - лицо фирмы.. Как правильно наращивать бизнес. Типичные ошибки начинающих предпринимателей. Главная » Новости |
© 2024 Team.Furia.Ru.
Частичное копирование материалов разрешено. |