ВУЗ:
Составители:
Рубрика:
сложность
О(5*n
3
),МОЖНО
говорить,
что
он
имеет
порядок
О(n
3
)
.
Это
утверждение
следует
из
определения
величины
O(f(n)),
если
положить
k
==
5.
3.0(f(n))+O(g(n))=O(f(n)+g(n)).
Функции,
описывающие
сложность
алгоритма,
можно
складывать.
Например,
если
алгоритм
имеет
сложность
о(n
2)+о(n),
то
говорят,
что
он
имеет
сложность
о(n
2+n).
В
соответствии
с
лт.Г,
это
МОЖНО
записать
просто
как
о(n
2
)
.
Аналогичные
правила
выполняются
для
умножения.
Из
указанных
выше
свойств
следует,
что
при
оценке
эффективности
алгоритма
нужно
оценить
лишь
порядок
его
сложности.
Точная
формула,
описывающая
сложность
алгоритма,
зачастую
весьма
сложна,
а
иногда
и
просто
невозможна.
Наихудший
и
средний
варианты.
При
решении
конкретных
задач
одинаковой
размерности
время
выполнения
алгоритма
может
оказаться
разным.
Например,
время,
необходимое
для
поиска
п
элементов,
может
зависеть
от
природы
самих
элементов.
Обычно
оценивается
максимальное
время,
необходимое
для
решения
задачи
размера
п,
т.е.
наихудший
вариант.
Анализ
наихудшего
варианта
(worts-case analysis)
приводит
к
оценке
O(f(n)),
если
при
решении
задачи,
имеющей
размер
п,
в
наихудшем
случае
алгоритм
выполняется
не
более
чем
за
k*f(n}
единиц
времени
для
всех
значений
п,
за
исключением
их
конечного
числа.
Хотя
анализ
наихудшего
варианта
приводит
к
пессимистическим
оценкам,
это
не
означает,
что
алгоритм
всегда
будет
работать
медленно.
Следует
иметь
в
виду,
что
наихудший
вариант
на
практике
встречается
редко.
12
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
