TY - JOUR

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

AU - Журавлев, Александр Александрович

AU - Трофимов, Сергей Павлович

PY - 2020

Y1 - 2020

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

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

UR - https://www.elibrary.ru/item.asp?id=43803196

U2 - 10.23670/IRJ.2020.98.8.008

DO - 10.23670/IRJ.2020.98.8.008

M3 - Статья

SP - 59

EP - 65

JO - Международный научно-исследовательский журнал

JF - Международный научно-исследовательский журнал

SN - 2303-9868

IS - 8-1 (98)

ER -