ВУЗ:
Составители:
Рубрика:
1
З*п2
о
1
n
п2-З*п+10
2
3
Рисунок
2.
Если
п>
2,
то
3 *n2
больше,
чем
n2 - 3 *
п
+ 1
О
количество
единиц
времени,
даже
если
размер
задачи
равен
1.
Следовательно,
еслиf(n)
==
log
n,
задачу
при
п
==
1
следует
рассматривать
отдельно.
Чтобы
подчеркнуть
значение
правильной
оценки
степени
роста
функции,
рассмотрим
таблицу
и
график,
представленные
на
рис.
3.
В
таблице
(рис.
3,
а)
показаны
разные
значения
аргумента
п
и
приближенные
значения
некоторых
функций,
зависящих
от
п,
в
порядке
увеличения
скорости
их
роста.
0(1)
< 0(10g2n) <
О(n)
< 0(n*log2n) <
о(n
2
)
<
О(n
3
)
<
0(211)
По
этой
таблице
можно
оценить
относительную
скорость
роста
значений
различных
функций.
(На
рис.
3 ,
б
показаны
графики
этих
функций).
Константа
означает,
что
время
выполнения
алгоритма
постоянно
и,
следовательно,
не
зависит
от
размера
задачи
Время
выполнения
логарифмического
алгоритма
(logarithmic
algorithm)
медленно
возрастает
с
увеличением
размера
задачи.
Если
размер
задачи
возводится
в
квадрат,
ее
сложность
увеличивается
всего
в
два
раза.
Позднее
мы
убедимся,
что
алгоритм
бинарного
поиска
обладает
именно
такими
свойствами.
Напомним,
что
при
бинарном
поиске
массив
делится
пополам,
а
затем
поиск
продолжается
в
одной
из
полученных
половин
массива.
Обычно
логарифмические
алгоритмы
решают
задачу,
сводя
ее
к
задаче
меньшего
размера.
Основание логарифма
не
влияет
на
сложность
алгоритма,
поэтому
его
можно
не
указывать.
10
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
