Главная » Java, Структуры данных и алгоритмы » Асимптотический анализ

0

Допустим, имеются два алгоритма решения определенной проблемы: алгоритм А, время выполнения которого 0(я), и алгоритм Д время выполнения которого 0(я2). Какой из алгоритмов лучше? Согласно нотации малого о, п есть о(п2), что предполагает — алгоритм А асимптотически лучше алгоритма 5, хотя при данном (малом) значении п алгоритм В может выполняться быстрее, чем алгоритм А.

С помощью нотации малого о можно классифицировать функции в соответствии с темпами их асимптотического роста. Ниже приводится список функций, расположенных в порядке увеличения темпов асимптотического роста, то есть если функция /(п) предшествует в списке функции g(n), то f{ri) есть o(g{ri))\

Темпы возрастания значений перечисленных функций представлены в табл. 3.2.

п

log п

 

п

п log л

«2

и3

2"

2

1

1,4

2

2

4

8

4

4

2

2

4

8

16

64

16

8

3

2,8

8

24

64

512

256

16

4

4

16

64

256

4 096

65 536

32

5

5,7

32

160

1 024

32 768

4 294 967 296

64

6

8

64

384

4 096

262 144

1,83 х 1019

128

7

11

128

896

16 384

2 097 152

3,40 х 1038

256

8

16

256

2 048

65 536

16 777 216

1,15 х 1077

512

9

23

512

4 608

262 144

134 217 728

1,34 х 10154

1 024

10

32

1 024

10 240

1 048 576

1 073 741 824

1,79 х 10308

Таблица 3.2. Рост некоторых функций

Значение асимптотического анализа представлено в табл. 3.3. В таблице отображены результаты исследования максимально возможного количества исходных данных, которое может быть обработано в течение 1 секунды, 1 минуты и 1 часа выполнения программы при условии, что одна операция выполняется в течение 1 микросекунды (1 мкс). Таблица также отражает значение хорошего построения алгоритма, так как если время выполнения алгоритма асимптотически медленное (например, алгоритм типа 0(п2)), то при длительном эыполненди он будет, безусловно,

уступать алгоритму с более асимптотически быстрым временем выполнения (например, 0(п log п)), даже если постоянный множитель асимптотически более быстрого алгоритма будет хуже.

Время выполнения (мкс)

Максимальный объем (п) 1 секунда 1 минута 1 час

400л

2 500

150 ООО

9 000 000

20п logп

4 096

166 666

7 826 087

In1

707

5 477

42 426

ri4

31

88

244

Т

19

25

31

Таблица 3.3. Максимальный объем исходных данных, который может быть обработан в течение одной секунды, одной минуты и одного часа при различных значениях времени выполнения алгоритма, выраженных в микросекундах

Хорошое построение алгоритма состоит не только в обеспечении максимального количества операций, выполняемых на данном компьютере. Табл. 3.4 демонстрирует тот факт, что даже при достижении значительной скорости работы аппаратных средств невозможно преодолеть недостатки асимптотически медленных алгоритмов. В таблице представлены новые значения максимальных объемов исходных данных, которые могут быть обработаны за определенный период времени при условии, что в данном случае алгоритмы с указанным временем выполнения запущены на компьютерах, скорость обработки информации которых в 256 раз выше, чем в предыдущем примере.

Время выполнения

Новый максимальный объем

400 п

256т

20п logп

approx. 256((log т) / (7 + log т))т

2п2

16 т

п4

4 т

2"

т + 8

Таблица 3.4. Увеличение максимального объема исходных данных, обрабатываемых за определенный период времени благодаря использованию компьютера, скорость обработки информации которого в 256 раз больше, чем в предыдущем примере, при различном времени выполнения алгоритмов. Объем представлен в виде функции т, которая обозначает предыдущий максимальный объем

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии