Сложность сортировки с помощью сортировкиk-слиянием:

Чтобы оценить время работы этого алгоритма, оценим время работы сортировки слиянием.

Для этого составим рекуррентное соотношение. Пускай T(n) — время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2*T(n/2)+O(n)  (O(n) — это время, необходимое на то, чтобы слить два массива).

Распишем это соотношение:

T(n)=2*T(n/2)+O(n)=4*T(n/4)+2*O(n)=…=2^k *T(1)+k*O(n)

Осталось оценить k. Мы знаем, что 2^k₌n, а значит k=log n.

Уравнение примет вид T(n)=n*T(1)+log n *O(n). Так как T(1)— константа, то

T(n)=O(n)+log n *O(n)= O(n* log n) – Итак, это сложность сортировки слиянием.

Для оценки сортировки k-слиянием понадобится оценка сложности алгоритма сортировки вставками.

Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число инверсий на единицу. Определение инверсии:

Пусть P=(p₁,p₂,…,p_n) является перестановкой чисел 1,2,…,n.

Инверсией в перестановке P называется всякая пара индексов i,j такая, что 1≤ i<j≤n и P[i]>P[j] .

Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по не возрастанию.

Число инверсий в таком массиве ½ *n(n-1). Получаем оценку О(n²).

Теперь оценим сложность алгоритма сортировки k-слиянием. Левитин, кормен

Для этого так же составим рекуррентное соотношение. Пускай T(n) — время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2*T(n/2)+O(n)  (O(n) — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

T(n)=2*T(n/2)+O(n)=4*T(n/4)+2*O(n)=…=2^l *T(w)+l*O(n)

Где w – число элементов, которые сортируются вставками.

Значит справедливо: T(w)=O(w²) (доказано в предыдущем пунтке)

2^l=w- в зависимости от n может изменяться от 1 до k-1 (Сортировка k-слиянием).

Таким образом, l=log =logn – logw. Т.к. w=const для конкретного n, то O(l)=O(logn), и аналогично для O(2^l)=O()=O(n).

Итак, T(n)= O(nw²)+log n *O(n)= O(n)+log n *O(n)= O(n* log n)

4. Просмотр массива для получения итогового множества точек выпуклой оболочки реализуется за время О(n)

5. Обратный перенос в исходную систему координат выполняется за один проход по массив, т.е. за время О(n).

Из приведенных доказательств следует, что суммарная сложность операции построения выпуклой оболочки равна O(n*logn)+ О(n)= O(n*logn)

3. Описание программы.

В рамках лабораторной работы реализованы 3 программы.

Первая программа демонстрирует правильность работы программы. Первое приложение можно запустить из командной строки. Интерфейс запуска следующий:

LAB_ADS.exe n q w mode

n - количество элементов

q,w - длины сторон прямоугольника (q x w)

mode - способ генерации данных (внутри или вне прямоугольника)

Программа генерирует соответствующим образом массив целочисленных точек, и реализует алгоритм поиска выпуклой оболочки, используя поочередно сортировки на основе d-кучи и сортировку k-слиянием. После построения выпуклой оболочки, запускается проверка по всему массиву точек, действительно ли полученные точки являются выпуклой оболочкой. По окончании работы приложения на экран будут выведены точки выпуклой оболочки, сообщение о том, прошла ли она проверку или нет, время работы в секундах каждого алгоритма(на основе соответствующих сортировок). Если количество точек будет в разумных пределах (<1000 или <10000 в зависимости от правила генерации), то на экране появится графическое изображение точек выпуклой оболочки и всех остальных точек.

Вторая и третья программа необходимы для проведения экспериментов. Вторая для проведения экспериментов при фиксированных и изменяющемся параметре, третья для серий экспериментов при фиксированном и изменяющихся параметрах.

Интерфейс вызова второй программы из командной строки следующий:

// LAB_ADS.exe n n1 mode

// n - начальное количество элементов

// n1 - конечное количество элементов

// mode - 1 или 2, способ генерации данных

// q=w=1000001

Интерфейс вызова третьей программы из командной строки следующий:

// LAB_ADS.exe qw qw1 mode

// n - число элементов = 1000000

// qw - начальные размеры квадрата(qw x qw)

// qw1 - конечные размеры квадрата

// mode - 1 или 2, способ генерации данных

По ходу работы следующих приложений на экран будет выводится время работы в секундах каждого алгоритма(на основе соответствующих сортировок). А так же время

работы будет записываться в файл для построения графиков.