ВУЗ:
Составители:
Рубрика:
единицу,
возникнет
n-1
уровней
рекурсии.
Следовательно,
функция
quicksort
выполняет
1 + 2 + ...+
(n-l)
==
n * (n-l)/2
сравнений.
Напомним,
однако,
что
при
переносе
элемента
в
множество
82
выполнять
перестановку
элементов
не
обязательно.
Для
этого
достаточно
лишь
изменить
индекс
firstUnknown.
Аналогично,
если
множество
82
при
каждом
рекурсивном
вызове
остается
пустым,
потребуется
п
* (n -1)/2
сравнений.
Кроме
того,
в
этом
случае
для
переноса
каждого
элемента
из
неизвестной
части
в
множество
81
придется
выполнять
перестановку
элементов.
Таким
образом,
понадобится
n *
(n -1)/2
перестановок.
(Напомним,
что
каждая
перестановка
выполняется
с
помощью
трех
операций
присваивания.)
Итак,
в
худшем
случае
сложность
алгоритма
quicksort
равна
О(
n
2).
Для
контраста
на
рис.
20
продемонстрирован
пример,
когда
множества
8]
и
82
состоят
из
одинакового
количества
элементов.
В
среднем
случае,
когда
множества
Sl
и
S2
состоят
из
одинакового
-
или
приблизительно
одинакового
-
количества
элементов,
записанных
в
произвольном
порядке,
рекурсивных
вызовов
функции
quick801
At
потребуется
меньше.
Как
и
при
анализе
алгоритма
merge8ort,
легко
показать,
что
глубина
рекурсии
в
алгоритме
quick80rt
равна
log2n
или
log2n+ 1.
При
каждом
вызове
функции
quick80rt
выполняется
т
сравнений
и
не
больше,
чем
m
перестановок,
где
т
-
количество
элементов
в
подмассиве,
подлежащем
сортировке.
42
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »
