ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.02.2021
Просмотров: 126
Скачиваний: 1
Анализ
алгоритмов
.
Для
выработки
количественных
критериев
сравнения
алгоритмов
,
претендующих
на
решение
одной
и
той
же
задачи
,
используются
такие
характеристики
алгоритмов
как
время
и
объем
памяти
,
используемых
алгоритмом
.
Пусть
A
–
алгоритм
решения
задачи
P
для
любых
данных
x
из
области
D
.
Пусть
t
A
(x)
–
время
работы
алгоритма
A
(
количество
элементарных
тактов
,
выполняемых
на
некоторой
модели
вычислительного
устройства
)
на
входных
данных
D
x
∈
,
s
A
(x)
-
объем
памяти
(
количество
ячеек
),
используемой
алгоритмом
A
при
обработке
x
,
а
|x|
-
размер
входных
данных
x,
т
.
е
.
число
,
характеризующее
их
объем
.
Тогда
функция
от
размера
данных
n
}
{
|
|
,
:
)
(
sup
)
(
n
x
D
x
x
n
t
T
A
A
≤
∈
=
,
}
{
|
|
,
:
)
(
sup
)
(
n
x
D
x
x
n
s
S
A
A
≤
∈
=
называются
соответственно
временной
и
емкостной
сложностями
алгоритма
A
.
Таким
образом
,
временная
и
емкостная
сложности
оценивают
время
и
объем
памяти
алгоритма
в
“
худшем
”
случае
.
Если
известно
распределение
вероятности
p(x)
на
входе
x
алгоритма
A
,
∑
≤
∈
=
n
x
D
x
x
p
|
|
,
1
)
(
,
то
функции
∑
≤
∈
⋅
n
x
D
x
A
x
t
x
p
|
|
,
)
(
)
(
(
средняя
временная
сложность
)
и
∑
≤
∈
⋅
n
x
D
x
A
x
s
x
p
|
|
,
)
(
)
(
(
средняя
емкостная
сложность
)
характеризуют
(
как
функции
от
размера
входа
n
)
средние
потребности
алгоритма
A
во
времени
и
памяти
.