ВУЗ:
Составители:
Рубрика:
Измерение
эффективности
алгоритмов
Сравнение
алгоритмов
между
собой
-
основная
тема
компьютерных
наук.
Измерение
эффективности
алгоритмов
чрезвычайно
важно,
поскольку
выбор
алгоритма
сильно
влияет на
работу
приложения.
Эффективность
алгоритмов,
положенных
в
основу
программы,
определяет
ее
успех,
будь
то
текстовый
процессор,
кассовый
аппарат,
банкомат,
видеоигра
или
что-нибудь
еще.
Допустим,
два
алгоритма
решают
одну
и
ту
же
задачу,
например
осуществляют
поиск
данных.
Как
их
сравнить
между
собой
и
решить,
какой
из
них
лучше?
Выясним
какакие
же
факторы,
влияют
на
стоимость
компьютерной
программы.
Некоторые
из
этих
факторов
касаются
стоимости
работы,
затраченной
на
разработку,
сопровождение
и использование
программы.
Другие
факторы
определяют
стоимость
ее
выполнения,
т.е.
эффективность,
выраженную
объемом
компьютерного
времени,
необходимого
для
выполнения
программы.
Анализ
алгоритмов
(analysis
of
algorithms) -
это
область
компьютерных
наук,
изучающая
способы
сравнения
эффективности
разных
методов
решения
задач.
Обратите
внимание,
что
в
этом
определении
использован
термин
"метод
решения
задачи",
а
не
"программа"
.
Следует
подчеркнуть.,
что
анализ
алгоритмов,
как
правило,
исследует
существенные
различия
эффективности,
которые
обусловлены
собственно
методами
решения
задач,
а
не
остроумными
программистскими
трюками.
Изощренные
приемы
кодирования,
позволяющие
снизить
стоимость
вычислений,
чаще
всего
снижают
читабельность
программы,
тем
самым
повышая
затраты
на
ее
сопровождение
и
модификацию.
Сравнение
алгоритмов
должно
быть
сосредоточено
на
их
существенных
различиях,
поскольку
именно
их
эффективность
является
основным
фактором,
определяющим
общую
стоимость
решения.
Если
два
алгоритма
выполняются
несколько
часов,
а
разница
между
временем
их
выполнения
составляет
несколько
секунд,
их
эффективность
одинакова.
При
анализе
эффективности
одинаково
важны
как
время
выполнения
алгоритма,
так
и
занимаемая
им
память.
Для
анализа
этих
факторов
используются
аналогичные
методы.
Как
сравнить
быстродействие
двух
алгоритмов,
решающих
одну
и
ту
же
задачу?
Для
этого
их
можно
запрограммировать
на
языке
С++
и
запустить
обе
программы.
У
этого
подхода
есть
три
существенных
недостатка.
1.
Как
запрограммированы
алгоритмы?
Допустим,
алгоритм
А
1
выполняется
быстрее,
чем
алгоритм
А
2
•
Это
может
быть
связано
с
тем,
что
программа,
реализующая
алгоритм
А
1
просто
лучше
написана.
Следовательно,
сравнивая
время
выполнения
программ,
вы
на
самом
деле
сравниваете
реализации
алгоритмов,
а
не
сами
алгоритмы.
Реализации
алгоритмов
сравнивать
бессмысленно,
5
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
