Оценка временной сложности сортировки | Коновалов Кирилл Андреевич и Гаев Леонид Витальевич. Работа №308029

ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМОВ СОРТИРОВКИ С ПОМОЩЬЮ МЕТОДА

НАИМЕНЬШИХ КВАДРАТОВ

Коновалов Кирилл Андреевич

Студент, Липецкий государственный технический университет

Гаев Леонид Витальевич

к.т.н., доцент, Липецкий государственный технический университет

Аннотация:

Алгоритмы играют важную роль в жизни современного человека. Любое действие людей можно считать алгоритмом. Анализ данных – самая популярная область применения алгоритмов. Наиболее известными методами для анализа данных являются алгоритмы сортировки. Важной характеристикой любого алгоритма является временная сложность. В данной статье предлагается оценка временной сложности алгоритмов с помощью метода наименьших квадратов. Основная идея данного метода заключается в минимизации суммы квадратов отклонений наблюдаемых значений зависимой переменной от значений, предсказанных моделью. В качестве алгоритмов для анализа выбраны пузырьковая сортировка, сортировка вставками и сортировка слиянием. Для каждого алгоритма проведено измерение времени (практического) выполнения сортировки массива с количеством элементов от 10000 до 100000 элементов (с шагом 10000, всего 10 наборов). Теоретическое время для каждого алгоритма соответствует функции одного из трех семейств: линейного, логарифмического и квадратичного. Далее вычисляется сумма квадрата разности практического и теоретического времен для каждого из трех семейств (линейного, логарифмического и квадратичного). Временная сложность соответствует семейству функции с наименьшим значением суммы квадрата разности практического и теоретического времен.

Ключевые слова: оценка, алгоритм, сортировка, метод наименьших квадратов

Введение

Алгоритмы играют важную роль в жизни современного человека. Любое действие людей можно считать алгоритмом в той или иной степени. Однако наиболее популярной областью для применения алгоритмов является анализ данных. Алгоритмы сортировки - самые известные методы для анализа набора данных. Важная характеристика любого алгоритма – его временная сложность. Существует множество способов оценить сложность алгоритмов. Одним из них является метод наименьших квадратов (МНК), которому и посвящена данная статья.

Цель данной статьи – оценить временную сложность алгоритмов сортировки с помощью метода наименьших квадратов.

В качестве материала исследования выступают алгоритмы сортировки.

В статье используется эмпирический метод исследования, поскольку основным источником результатов является

эксперимент.

Описание метода наименьших квадратов

Идея оценивания по методу наименьших квадратов заключается в минимизации суммы квадратов отклонений наблюдаемых значений зависимой переменной от значений, предсказанных моделью [1], [2].

В данной статье за оцениваемую величину берется временная сложность алгоритма. Анализ проводится по следующему принципу:

вычисляется практическое время выполнения

T

пр

, которое необходимо для сортировки определенного количества элементов;

теоретическое время выполнения является функцией одного из следующих семейств: линейное (вид A + C*N), логарифмическое (вид A + C*N*

logN

) или квадратичное семейство (вид A + C*N

2

) (здесь A и C – некоторые числовые коэффициенты, N – количество сортируемых элементов);

вычисляется сумма квадрата разности практического и теоретического времен для каждого из семейств по формуле (1);

временная сложность O соответствует семейству функции с наименьшим значением суммы квадратов разности. Для оценки временной сложности будем использовать следующую формулу:

n

S(Ti,пр Ti теор, )2 (1)

i1

где S – сумма квадратов разности практического и теоретического времен для i-го значения выборки, n – количество элементов в выборке, Ti,пр – практическое время i-го значения выборки, Ti,теор – теоретическое время i-го значения выборки.

В качестве сравнительной статьи используется источник [3].

Оценка временной сложности некоторых алгоритмов сортировки с помощью метода наименьших квадратов

В данной статье алгоритмами сортировки для оценки временной сложности являются: пузырьковая сортировка, сортировка вставками и сортировка слиянием. Объекты сортировки – целочисленные массивы с количеством элементов от 10000 до 100000 (шаг равен 100000, всего 10 наборов). Каждый из алгоритмов реализован в Visual Studio на языке C#. Для измерения времени сортировки каждого из массивов использовался класс Stopwatch. Для установления вида функции временной сложности использовался Excel.

Анализ временной сложности пузырьковой сортировки

Алгоритм пузырьковой сортировки имеет временную сложность O(n2). Описание работы пузырьковой сортировки

представлено в виде блок-схемы, изображенной на рисунке 1 [4], [5].

Рис. 1 – Блок-схема пузырьковой сортировки

На рисунке 2 представлено время (практическое) выполнения пузырьковой сортировки для массива с количеством

элементов от 10000 до 100000.

Рис. 2 – Практическое время выполнения пузырьковой сортировки

Данные анализа представлены на рисунке 3.

Рис. 3 – Анализ временной сложности пузырьковой сортировки

На рисунке 3 N – количество элементов массива; Tпр – практическое время сортировки; Tтеор(N), Tтеор(logN), Tтеор(N2) – теоретическое время сортировки для линейного, логарифмического и квадратичного семейств соответственно (Tтеор(N) = A(N) + C(N)*N, Tтеор(logN) = A(logN) + C(logN)*N*logN, Tтеор(N2) = A(N2) + C(N2)* N2); A(N), C(N), A(logN), C(logN), A(N2), C(N2) – некоторые коэффициенты.

Далее с помощью утилиты «Поиск решения» была найдена минимальная сумма квадрата разности для каждого из семейств. Пример использования «Поиска решения» представлен на рисунке 4. Изменяющиеся ячейки – ячейки с коэффициентами A и C. Ячейка, которую нужно минимизировать – ячейка с суммой квадрата разности практического и теоретического времен.

Рис. 4 – Работа с утилитой «Поиск решения»

Как видно из рисунка 3, минимальное значение (4,95*109 < 3,03 * 1010 < 3,31 * 1010) имеет сумма для квадратичного

семейства. Следовательно, временная сложность пузырьковой сортировки равняется O(N2), что соответствует теории.

Анализ временной сложности сортировки вставками

Описание работы сортировки вставками представлено в виде блок-схемы, изображенной на рисунке 5 [4], [6].

Рис. 5 – Блок-схема сортировки вставками

На рисунке 6 представлено время (практическое) выполнения сортировки вставками для массива с количеством

элементов от 10000 до 100000.

Рис. 6 – Практическое время выполнения сортировки вставками

Данные анализа представлены на рисунке 7.

Рис.7 – Анализ временной сложности сортировки вставками

Как видно из рисунка 7, минимальное значение (1,29 * 108 < 7,86 * 108 < 9,15 * 108) имеет сумма для квадратичного

семейства. Следовательно, временная сложность сортировки вставками равняется O(N2), что соответствует теории.

Анализ временной сложности сортировки слиянием

Описание работы сортировки слиянием представлено в виде блок-схемы, изображенной на рисунках 8 и 9 [7], [8].

Рис. 8 – Блок-схема сортировки слиянием

Рис. 9 – Блок-схема слияния подмассивов

На рисунке 10 представлено время (практическое) выполнения сортировки слиянием для массива с количеством

элементов от 10000 до 100000.

Рис.10 – Практическое время выполнения сортировки слиянием

Данные анализа представлены на рисунке 11.

Рис.11 – Анализ временной сложности сортировки слиянием

Как видно из рисунка 11, минимальное значение (9003,651 < 9183,197 < 39938,6) имеет сумма для логарифмического семейства. Следовательно, временная сложность сортировки слиянием равняется O(logN), что соответствует теории.

Получаем, совпадение теоретической временной сложности и временной сложности, вычисленной по методу наименьших квадратов, для каждого из трех алгоритмов (пузырьковая сортировка, сортировка вставками и сортировка слиянием). Таким образом, способ оценки временной сложности алгоритмов с помощью метода наименьших квадратов можно считать корректным.

Заключение

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

Результаты исследования

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

Список литературы

Метод наименьших квадратов [Электронный ресурс]. URL: https://clck.ru/Q6cgM (дата обращения: 15.06.2020)

Метод наименьших квадратов [Электронный ресурс]. URL: http:// mathprofi.ru/metod_naimenshih_kvadratov.html (дата обращения: 15.06.2020)

Падве В. А., Мазуров Б. Т. Метод наименьших квадратов (история и развитие) //

Интерэкспо

Гео-Сибирь. 2017. № 1. С.

150-154

Блок схемы алгоритмов [Электронный ресурс].

URL: https://sites.google. com/site/

arraylazarus

/

sheme

(

дата

обращения

:

15.06.2020)

Пузырьковая сортировка [Электронный ресурс]. URL: https://clck.ru/Q6chJ (дата обращения: 15.06.2020)

Сортировка вставками [Электронный ресурс]. URL: http://algolist.ru/

sort

/

insert_sort.php

(дата обращения: 15.06.2020)

Блок-схемы алгоритмов. ГОСТ. Примеры [Электронный ресурс]. URL: https://pro-prof.com/a

rchives

/1462 (дата обращения: 15.06.2020)

Сортировка слиянием [Электронный ресурс]. URL: http://algolist.ru/sort/

merge_sort.php

(дата обращения: 15.06.2020)