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

科研成果: Article同行评审

摘要

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.
投稿的翻译标题EVALUATING TIME COMPLEXITY OF SORTING THROUGH THE LEAST-SQUARE METHOD
源语言Russian
页(从-至)59-65
页数7
期刊Международный научно-исследовательский журнал
8-1 (98)
DOI
Published - 2020

Level of Research Output

  • VAK List

指纹

探究 'ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМОВ СОРТИРОВКИ С ПОМОЩЬЮ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ' 的科研主题。它们共同构成独一无二的指纹。

引用此