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