ВУЗ:
Составители:
Рубрика:
следующем
рекурсивном
вызове
функции
mergesort
каждая
из
этих
частей
снова
делится
пополам,
образуя
четыре
части
исходного
массива.
При
следующем
рекурсивном
вызове
каждая
из
этих
четырех
частей
опять
делится
пополам,
образуя
восемь
частей
массива,
и
т.д.
Рекурсивные
вызовы
продолжаются
до
тех
пор,
пока
части
массива
не
станут
содержать
только
по
одному
элементу,
иными
словами,
пока
исходный
массив
не
будет
разбит
на
п
частей,
что
соответствует
количеству
его
элементов,
если
число
п
является
степенью
ДВОЙКИ
(n=2
k
) ,
глубина
рекурсии
равна
k=log2.n.
Например,
как
показано
на
рис.ll,
если
исходный
массив
содержит
восемь
элементов
(8=23 ),
то
глубина рекурсии
равна
3.
Если
число
n
является
степенью
двойки,
глубина
рекурсии
равна
1+
Iog
2n
(округленное
значение).
Исходный
вызов
функции
mergesort
(уровень
О)
обращается
к
функции
merge
только
один
раз.
Затем
функция
merge
осуществляет
слияние
п
элементов,
выполняя
3*n-l
операций.
На
первом
уровне
рекурсии
выполняются
два
вызова
функции
mergesort
И,
следовательно,
функции
merge.
Каждый
из
этих
двух
вызовов
приводит
К
слиянию
n/2
элементов
и
требует
выполнения
3*(n/2)-1
операций.
Таким
образом,
на
этом
уровне
выполняется
2*(3*(n/2)-1
)==3*n-2
операций.
На
т-м
уровне
рекурсии
выполняются
2т
вызовов
функции
merge.
Каждый
из
этих
вызовов
приводит
К
слиянию
n
12т
элементов,
а
общее
количество
операций
равно
3*(nI2
n
1)-2.
В
целом,
2т
рекурсивных
вызова
функции
merge
порождает
3*n-2
т
операций.
Таким
образом,
на
каждом
уровне
рекурсии
выполняется
О(n)
операций.
Поскольку
количество
уровней
рекурсии
равно
Iog
2n
или
Iog
2n
+
1,
в
наихудшем
и
среднем
вариантах
функция
mergesort
имеет
сложность
O(n*log2n).
Посмотрите
на
рис.3
и
еще
раз
убедитесь,
что
величина
O(n*log2n)
растет
намного
быстрее,
чем
величина
о(n
2
)
.
Хотя
алгоритм
сортировки
слиянием
имеет
чрезвычайно
высокое
быстродействие,
у
него
есть
один
недостаток.
Для
выполнения
операции
Объединить
упорядоченные
подмассивы
theArray[first mid]
и
theArray[mid+l last]
необходим
вспомогательный
массив,
состоящий
из
n
элементов.
Если
объем
доступной
памяти
ограничен,
это
требование
может
оказаться
неприемлемым.
Выстряя
сортировка
Рассмотрим
два
первых
шага
решения
задачи
о
поиске
k-ro
наименьшего
элемента
массива
theArray[fist
... last},
Выберите
в
массиве
thеАrrаvfПrst
... last
[опорный
элемент
р
Поделите
массив
theArray[first... last]
относительно
элемента
р
Разбиение,
показанное
на
рис.
12,
характеризуется
тем,
что
все
элементы
множества
S 1
==
theArray
[first...
pivotlndex-1}
меныпе
опорного
элемента
р,
30
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
