- •Факультет вычислительной математики и кибернетики
- •Описание алгоритмов
- •Постановка задачи
- •Алгоритм построение выпуклой оболочки с помощью сортировки
- •Алгоритм сортировки с использованиемd-куч.
- •Псевдокод операций используемых надd-кучей и некоторые оценки сложности.
- •Алгоритм сортировкиk-слиянием.
- •Алгоритм сортировки вставками.
- •Обоснование теоретических оценок временной сложности алгоритмов.
- •Сложность сортировки с помощьюd-куч:
- •Сложность сортировки с помощью сортировкиk-слиянием:
- •Описание программы.
- •Проведенные эксперименты.
- •Сравнение алгоритмов
Проведенные эксперименты.
Согласно поставленной задаче были проведены 2 группы экспериментов:
Длина и ширина прямоугольника для генерации точек фиксируются (106), изменяется количество генерируемых точек с шагом.
Фиксируется количество генерируемых точек (106), изменяется длина и ширина прямоугольника для случайной генерации точек с шагом
Для каждого набора параметров случайным образом генерируется набор точек, который подается на вход исследуемым алгоритмам. Соответственно замеряется время работы (в секундах) каждого алгоритма над указанным множеством точек.
Результаты первой группы экспериментов приведены соответственно на рис.1 и рис2, а результаты второй – на рис.3 и рис 4.
Рис.1. Время работы исследуемых алгоритмов при фиксированных иизменяющемся параметре; С=K=10-6
Рис.2 Время работы исследуемых алгоритмов при фиксированных иизменяющемся параметре; С=11*10-5;K=9*10-5
Риc3. Время работы исследуемых алгоритмов при фиксированном иизменяющихся параметрах
Риc4. Время работы исследуемых алгоритмов при фиксированном иизменяющихся параметрах
Сравнение алгоритмов
По результатам проведённых экспериментов можно оценивать эффективность работы каждого из алгоритмов. Эксперименты показывают, что алгоритм построения выпуклой оболочки, использующий метод сортировки с помощью 50-кучи, работает эффективнее, чем алгоритм построения выпуклой оболочки, использующий метод сортировки 52-слиянием.
Необходимо отметить, что, начиная с некоторых значений длины (ширины) прямоугольника распределения точек при фиксированном их количестве (см. рис.3,4), время работы алгоритмов стабилизируется в окрестности некоторого значения. Данный факт говорит о том, что время работы алгоритма не зависит от размеров прямоугольника распределения.
Выводы
Теоретическая оценка сложности обоих алгоритмов принадлежит множеству функций (множество таких функций, что существует положительная константа, для которых).
Графики серии экспериментов при изменяющемся значении числа точек массива (см. рис.1) близки к графикам функций . Таким образом, результаты практических экспериментов не противоречат теории, т.к. данная функция включена в класс теоретических оценок.