EVALUATING TIME COMPLEXITY OF SORTING THROUGH THE LEAST-SQUARE METHOD

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

Научная статья

Журавлев А. А.^1, *,Трофимов С. П.²

^{1, 2} Уральский Федеральный Университет им. Б. Н. Ельцина, г. Екатеринбург, Россия

* Корреспондирующий автор (SanyaProgrammer2503[at]gmail.com)

Аннотация

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

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

EVALUATING TIME COMPLEXITY OF SORTING THROUGH THE LEAST-SQUARE METHOD

Research article

Zhuravlev A. A.^1, *, Trofimov S. P. ²

^{1, 2} Ural Federal University named after the First President of Russia B. N. Yeltsin, Yekaterinburg, Russia

* Corresponding author (SanyaProgrammer2503[at]gmail.com)

Abstract

Algorithms play an essential role in modern life. Any human action might be considered an algorithm. Data analysis is the most popular field of algorithm application.  Most well-known methods of data analysis are sorting algorithms. The essential characteristic of any algorithm is time complexity. This article suggests the evaluation of time complexity through the least-square method. The main idea of this method is in minimizing the sum of squared deviations of dependant variable observed values from the model-predicted values. Bubble sort, insertion sort, and merge sort are the algorithms chosen for analysis. For every algorithm array sorting actual running time is measured, where the array included 10000 to 100000 elements (at 10000 intervals, ten sets altogether). Predicted time for every algorithm complies with the function of one of the classes: linear, logarithmic, and quadratic. Then the sum of the squared difference between the actual and the predicted time for every class (linear, logarithmic, and quadratic) is calculated. Time complexity matches the class of functions with the least value of the sum of the squared difference between the actual and the predicted time.

Keywords: evaluation, algorithm, sorting, least-square method

Введение

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

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

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

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

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

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

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

• вычисляется практическое время выполнения T_пр, которое необходимо для сортировки определенного количества элементов;
• теоретическое время выполнения является функцией одного из следующих семейств: линейное (вид A + C*N), логарифмическое (вид A + C*N*logN) или квадратичное семейство (вид A + C*N²) (здесь A и C – некоторые числовые коэффициенты, N – количество сортируемых элементов);
• вычисляется сумма квадрата разности практического и теоретического времен для каждого из семейств по формуле (1);
• временная сложность O соответствует семейству функции с наименьшим значением суммы квадратов разности.

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

     (1)

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

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

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

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

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

Алгоритм пузырьковой сортировки имеет временную сложность O(n²). Описание работы пузырьковой сортировки представлено в виде блок-схемы, изображенной на рисунке 1 [4], [5].

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

 

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

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

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

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

 

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

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

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

 

Как видно из рисунка 3, минимальное значение (4,95*10⁹ < 3,03 * 10¹⁰ < 3,31 * 10¹⁰) имеет сумма для квадратичного семейства. Следовательно, временная сложность пузырьковой сортировки равняется O(N²), что соответствует теории.

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

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

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

 

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

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

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

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

 

Как видно из рисунка 7, минимальное значение (1,29 * 10⁸ < 7,86 * 10⁸ < 9,15 * 10⁸) имеет сумма для квадратичного семейства. Следовательно, временная сложность сортировки вставками равняется O(N²), что соответствует теории.

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

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

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

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

 

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

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

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

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

 

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

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

Заключение

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

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

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

Конфликт интересов Не указан.

Conflict of Interest None declared.

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

1. Метод наименьших квадратов [Электронный ресурс]. URL: https://clck.ru/Q6cgM (дата обращения: 15.06.2020)
2. Метод наименьших квадратов [Электронный ресурс]. URL: http:// mathprofi.ru/metod_naimenshih_kvadratov.html (дата обращения: 15.06.2020)
3. Падве В. А., Мазуров Б. Т. Метод наименьших квадратов (история и развитие) // Интерэкспо Гео-Сибирь. 2017. № 1. С. 150-154
4. Блок схемы алгоритмов [Электронный ресурс]. URL: https://sites.google. com/site/arraylazarus/sheme (дата обращения: 15.06.2020)
5. Пузырьковая сортировка [Электронный ресурс]. URL: https://clck.ru/Q6chJ (дата обращения: 15.06.2020)
6. Сортировка вставками [Электронный ресурс]. URL: http://algolist.ru/ sort/insert_sort.php (дата обращения: 15.06.2020)
7. Блок-схемы алгоритмов. ГОСТ. Примеры [Электронный ресурс]. URL: https://pro-prof.com/a rchives/1462 (дата обращения: 15.06.2020)
8. Сортировка слиянием [Электронный ресурс]. URL: http://algolist.ru/sort/ merge_sort.php (дата обращения: 15.06.2020)

Список литературы на английском языке / References in English

1. Metod naimen'shih kvadratov [Least-square method] [Electronic resource]. URL: https://clck.ru/Q6cgM (accessed: 15.06.2020)
2. Metod naimen'shih kvadratov [Least-square method] [Electronic resource]. URL: http://mathprofi.ru/metod_naimenshih_kvadratov.html (accessed: 15.06.2020)
3. Padve V. A., Mazurov B. T. Metod naimen'shih kvadratov (istoriya i razvitie) [Least-square method (history and development)] // Interexpo GEO-Siberia. 2017. № 1. pp. 150-154
4. Blok skhemy algoritmov [Block schemes of algorithms] [Electronic resource]. URL: https://sites.google.com/site/arraylazarus/sheme (accessed: 15.06.2020)
5. Puzyr'kovaya sortirovka [Bubble sort] [Electronic resource]. URL: https://clck.ru/Q6chJ (accessed: 15.06.2020)
6. Sortirovka vstavkami [Insertion sort] [Electronic resource]. URL: http://algolist.ru/sort/insert_sort.php (accessed: 15.06.2020)
7. Blok-skhemy algoritmov. GOST. Primery [Block schemes of algorithms. GOST. Examples] [Electronic resource]. URL: https://pro-prof.com/archives/1462 (accessed: 15.06.2020)
8. Sortirovka sliyaniem [Merge sort] [Electronic resource]. URL: http://algolist.ru/sort/merge_sort.php (accessed: 15.06.2020)