Методы сортировок и их реализации. Беляева И.В - 16 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

1.
Проверяет
среднюю
ячейку
массива,
имеющего
длину
n.
2.
Проверяет
среднюю
ячейку
массива,
имеющего
длину
n/2.
3.
Проверяет
среднюю
ячейку
массива,
имеющего
длину
n/2
2
и
т.д,
Чтобы
проверить
среднюю
ячейку
массива,
сначала
нужно
поделить
массив
пополам.
После
того
как
массив,
состоящий
из
n
элементов,
поделен
пополам,
делится
пополам
одна
из
его
половин.
Эти
деления
продолжаются
до
тех
пор,
пока
'не
останется
только
один
элемент.
Для
этого
потребуется
k
выполнить
k
разбиений
массива.
Это
возможно,
поскольку
n/2
==1.
2
k
(Напомним,
что
n =
.)
В
наихудшем
случае
алгоритм
выполнит
k
разбиений
и,
следовательно,
k
сравнений.
Поскольку
п
==
2 ,
k
получаем,
что
k==
Iog
2
n.
Что
произойдет,
если
число
п
не
будет
степенью
двойки?
Легко
найти
наименьшее
число
k,
удовлетворяющее
условию
2
k
1<n<2
k
-
(Например,
если
n
равно
30,
то
k=5,
поскольку
24
= 16 < 30 < 32 <
25.)
Алгоритм
по-прежнему
выполнит
по
меньшей
мере
k
разбиений,
пока
не
возникнет
массив,
состоящий
из
одного
элемента.
Итак,
получаем
следующие
оценки.
k-l
<
Iog
2
п
< k,
k
< 1+log
2n<
k+
1,
k~l+
10g2n.
Следовательно,
в
наихудшем
случае
сложность
бинарного
поиска
оценивается
величиной
бинарного
поиска
равна
O(lOg2n),
если
ni-2
k
•
в
принципе
сложность
алгоритма
в
наихудшем
случае
имеет
порядок
O(10g
2n)
для
любого
значения
п.
Можно
ли
утверждать,
что
бинарный
поиск
лучше
последовательного?
Намного
лучше!
Например,
Iog
21
000000==19,
поэтому
алгоритм
последовательного
поиска
выполнит
миллион
сравнений,
в
то
время
как
алгоритм
бинарного
поиска
-
не
более
20.
Если
массивы
велики,
бинарный
поиск
намного
эффективнее
последовательного.
Однако
следует
иметь
в
виду,
что
условие
упорядоченности
массива
приводит
к
дополнительным
затратам,
которые
могут
стать
существенными.
В
следующем
разделе
мы
попробуем
их
оценить.
Алгоритмы
сортировки
И
их
эффективность
Сортировка
(sorting) -
это
процесс
упорядочения
набора
элементов
в
возрастающем
или
убывающем
порядке.
Сортировка
необходима
во
многих
ситуациях.
Например,
иногда
нужно
упорядочить
данные,
прежде
чем
включить
их
в
отчет.
Однако
чаще
всего
сортировка
выполняется
в
качестве
первого
шага
некоторых
алгоритмов.
Например,
поиск
данных
является
одной
из
наиболее
распространенных
задач,
выполняемых
компьютерами.
Если
набор
данных
достаточно
велик,
необходимо
применять
эффективный
метод,
например
алгоритм
бинарного
поиска.
Однако
для
применения
алгоритма
15

Страницы