ВУЗ:
Составители:
Рубрика:
Анализ
среднего
варианта(
average-case analysis)
позволяет
оценить
среднее
время
выполнения
алгоритма
при
решении
задачи
размера
n.Говорят,
что
среднее
время
выполнения
алгоритма
А
равно
O
(f
(n)) ,
если
при
решении
задачи
размера
п
оно
не
превышает
величины
k* f(n)
для
всех
значений
п,
за
исключением
их
конечного
числа.
Как
правило,
анализ
среднего
варианта
выполнить
намного
сложнее,
чем
анализ
наихудшего
варианта.
Одна
из
трудностей
заключается
в
определении
вероятностей
появления
разных
задач
одинаковой
размерности.
Вторая
трудность
заключается
в
вычислении
распределений
разных
значений.
Анализ
наихудшего
варианта
легче
поддается
вычислениям
и
поэтому
выполняется
намного
чаще.
Эффективность
алгоритмов
поиска
в
качестве
еще
одного
примера
рассмотрим
два
алгоритма
поиска:
последовательный
и
бинарный
поиск
элемента
в
массиве.
Последовательный
поиск.
При
последовательном
поиске
элемента
в
массиве,
имеющем
длину
п,
элементы
просматриваются
по
очереди,
начиная
с
первого,
пока
не
обнаружится
искомый,
либо
не
будет
достигнут
конец
массива.
В
наилучшем
случае
искомым
элементом
является
первый.
Для
его
обнаружения
понадобится
только
одно
сравнение.
Следовательно,
в
наилучшем
случае
сложность
алгоритма
последовательного
поиска
равна
0(1).
В
наихудшем
случае
искомый
элемент
является
последним.
Для
того
чтобы
его
найти,
понадобится
п
сравнений.
Следовательно,
в
наихудшем
случае
сложность
алгоритма
последовательного
поиска
равна
О(п).В
среднем
случае
искомый
элемент
находится
в
средней ячейке
массива
и
обнаруживается
после
n/2
сравнений.
Бинарный
ПОИСК.
Является
ли
бинарный
поиск
более
эффективным,
чем
последовательный?
Алгоритм
бинарного
поиска,
предназначен
для
поиска
элемента
в
упорядоченном
массиве
и
основан на
повторяющемся
делении
частей
массива
пополам.
Алгоритм
определяет,
в
какой
из
двух
частей
находится
элемент,
если
он
действительно
хранится
в
массиве,
а
затем
повторяет
процедуру
деления
пополам.
Итак,
в
ходе
бинарного
поиска
возникает
несколько
массивов
меньшего
размера,
причем
каждый
раз
размер
очередного
массива
уменьшается
вдвое
по
сравнению
с
предыдущим.
В
ходе
очередного
разбиения
массива
алгоритм
выполняет
сравнения.
Сколько
сравнений
выполняет
алгоритм
при
поиске
элемента
в
массиве,
имеющем
длину
n?
Точный
ответ
на
этот
вопрос,
разумеется,
зависит
от
позиции
искомого
элемента
в
массиве.
Однако
можно
вычислить
максимальное
количество
сравнений,
т.е.
наихудший
вариант.
Допустим,
2
k
что
п
==
,
где
k -
некоторое
натуральное
число.
Алгоритм
поиска
выполняет
следующие
шаги.
14
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
