Файл: Курсовая работа Алгоритм быстрой сортировки студентка 3 курса 1 группы физикоматематического факультета.rtf
Добавлен: 06.11.2023
Просмотров: 791
Скачиваний: 11
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Глава 1. Основные теоретические аспекты алгоритма и сортировки
1.1 Понятие алгоритма и сортировки
1.2 Основные способы и алгоритмы сортировки массивов
1.4 Основные правила, понятия и теоремы
2.1 Описание алгоритма «быстрой сортировки»
2.2 Реализация на языке программирования
Глава 3. Анализ быстрой сортировки
3.1 Анализ наихудшего разбиения
и в первой скобке (1) можно включить в . С учетом этого получаем .Поскольку каждое слагаемое , где k=1, 2,…,n-1, встречается в сумме дважды, ее можно переписать так:
(2)
. Решение рекуррентного соотношения.Соотношение 2 можно решить, используя метод подстановки. Предположим, что , где константы и пока неизвестны, и попытаемся доказать это по индукции. При n=1 это верно, если взять достаточно большие а и b. При n>1 имеемНиже мы покажем, что первую сумму можно оценить так:
(3)
Используя это, получимЕсли выбрать а так, чтобы аn/4 было больше . Следовательно, среднее время работы есть .Доказательство оценки для суммы.Нам осталось доказать оценку (3). Поскольку каждое слагаемое не превышает nlgn, получаем оценку .Для наших целей она не подходит – нам необходимо более точная оценка .Если, заменив лишь на , мы, оставив k в неприкосновенности, получим оценку .Осталось лишь заметить, что заменяя на , мы прибавили, по крайней мере по k к каждому слагаемом первой половины суммы (где k n/2), всего примерно .Более подробно,
(2)
. Решение рекуррентного соотношения.Соотношение 2 можно решить, используя метод подстановки. Предположим, что , где константы и пока неизвестны, и попытаемся доказать это по индукции. При n=1 это верно, если взять достаточно большие а и b. При n>1 имеемНиже мы покажем, что первую сумму можно оценить так:
(3)
Используя это, получимЕсли выбрать а так, чтобы аn/4 было больше . Следовательно, среднее время работы есть .Доказательство оценки для суммы.Нам осталось доказать оценку (3). Поскольку каждое слагаемое не превышает nlgn, получаем оценку .Для наших целей она не подходит – нам необходимо более точная оценка .Если, заменив лишь на , мы, оставив k в неприкосновенности, получим оценку .Осталось лишь заметить, что заменяя на , мы прибавили, по крайней мере по k к каждому слагаемом первой половины суммы (где k n/2), всего примерно .Более подробно,
.
При 
имеем 
. Поэтому
При n
2. Оценка (3) доказана.