Теория алгоритмов. Зюзысов В.М. - 60 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Таблица 1. Границы размеров задач, определяемые скоростью роста сложности.
Максимальный размер задачи
Алгоритм Асимптотическая
временная сложность
1 с 1 мин 1 ч
A
1
Ο(n)
1000
6×10
4
3,6×10
6
A
2
Ο(n log n)
140 4893
2,0×10
5
A
3
Ο(n
2
)
31 244 1897
A
4
Ο(n
3
)
10 39 153
A
5
Ο(2
n
)
9 15 21
Предположим, что следующее поколение компьютеров будет в 10 раз быстрее
нынешнего. В таблице 2 показано, как возрастут размеры задач, которые мы сможем
решить благодаря этому увеличению скорости.
Таблица 2. Эффект десятикратного ускорения
Максимальный размер задачи
Алгоритм Асимптотическая
временная сложность
До ускорения После
ускорения
A
1
Ο(n)
S
1
10 S
1
A
2
Ο(n log n)
S
2
Примерно 10 S
2
для больших S
2
A
3
Ο(n
2
)
S
3
3,16 S
3
A
4
Ο(n
3
)
S
4
2,15 S
4
A
5
Ο(2
n
)
S
5
S
5
+ 3,3
Заметим, что для алгоритма A
5
десятикратное увеличение скорости увеличивает
размер задачи, которую можно решить, только на три, тогда как для алгоритма A
3
размер
задачи более чем утраивается.
Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более
действенного алгоритма. Вернемся к таблице 1. Если в качестве основы для сравнения
взять 1 мин, то, заменяя алгоритм A
4
алгоритмом A
3
, можно решить задачу в 6 раз
большую, а заменяя A
4
на A
2
, можно решить задачу, большую в 125 раз. Эти результаты
производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет
десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то
различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая
скорость алгоритма служит важной мерой качественности алгоритма, причем такой
мерой, которая
обещает стать еще важнее при последующем увеличении скорости
вычислений.
Несмотря на то, что основное внимание здесь уделяется порядку роста величин,
надо понимать, что больший порядок сложности алгоритма может иметь меньшую
мультипликативную постоянную, чем малый порядок роста сложности другого алгоритма.
В таком случае алгоритм с быстро растущей сложностью может оказать предпочтительнее
для задач с малым размером – возможно, даже для всех задач, которые нас интересуют.
5.3 Сложность задач
Сложность задачи – это асимптотическая временная сложность наилучшего
алгоритма, известного для ее решения.

Страницы