DOI

Алгоритмы играют важную роль в жизни современного человека. Любое действие людей можно считать алгоритмом. Анализ данных - самая популярная область применения алгоритмов. Наиболее известными методами для анализа данных являются алгоритмы сортировки. Важной характеристикой любого алгоритма является временная сложность. В данной статье предлагается оценка временной сложности алгоритмов с помощью метода наименьших квадратов. Основная идея данного метода заключается в минимизации суммы квадратов отклонений наблюдаемых значений зависимой переменной от значений, предсказанных моделью. В качестве алгоритмов для анализа выбраны пузырьковая сортировка, сортировка вставками и сортировка слиянием. Для каждого алгоритма проведено измерение времени (практического) выполнения сортировки массива с количеством элементов от 10000 до 100000 элементов (с шагом 10000, всего 10 наборов). Теоретическое время для каждого алгоритма соответствует функции одного из трех семейств: линейного, логарифмического и квадратичного. Далее вычисляется сумма квадрата разности практического и теоретического времен для каждого из трех семейств (линейного, логарифмического и квадратичного). Временная сложность соответствует семейству функции с наименьшим значением суммы квадрата разности практического и теоретического времен.
Переведенное названиеEVALUATING TIME COMPLEXITY OF SORTING THROUGH THE LEAST-SQUARE METHOD
Язык оригиналаРусский
Страницы (с-по)59-65
Число страниц7
ЖурналМеждународный научно-исследовательский журнал
Номер выпуска8-1 (98)
DOI
СостояниеОпубликовано - 2020

    Уровень публикации

  • Перечень ВАК

ID: 20200942