Ну, есть не так много классов сложности, которые вас действительно волнуют, так что скажем: линейный, квадратичный, полиномиальный (степень> 2), экспоненциальный и логарифмический.
Для каждого из них вы можете использоватьнаибольшая (x, y) пара для решения неизвестной переменной.Пусть y = f (x) обозначает время выполнения вашего алгоритма как функцию размера выборки.Давайте предположим, что f (1) = 0, и если этого не произойдет, мы всегда сможем вычесть это значение y (1) из каждого из y, это просто исключит константы в f (x).Пусть y (end) обозначает последнее (и наибольшее) значение y в вашем (x, y) наборе данных.
На данный момент мы можем найти для неизвестного в каждой канонической форме:
f(x) = c*x
f(x) = c*x^2
f(x) = x^c
f(x) = c^x
f(x) = log(x)/log(c)
Поскольку в каждом уравнении есть только один неизвестный, мы можем вам в любой момент найти для него точку.Рассмотрим следующие данные, полученные из полинома случайной степени> 2:
x = [ 1 2 3 4 5 6 7 8 9 10 ];
y = [ 0 6 19 44 81 135 206 297 411 550 ];
Если мы используем последнюю точку для решения для c для каждой возможности (предполагая, что это будет наименьшая оценка шума)
550 = c*10 -> c = 55
550 = c*10^2 -> c = 5.5
550 = 10^c -> c = log(550)/log(10) ~= 2.74
550 = c^10 -> c = 550^(1/10) ~= 1.88
550 = log(x)/log(c) -> c = 10^(1/550) ~= 1.0042
Теперь мы можем сравнить, насколько хорошо каждая из этих функций соответствует оставшимся данным, вот график:
Я новичок и не могу публиковать изображения, поэтому посмотрите на график здесь: http://i.stack.imgur.com/UH6T8.png
Истинные данные показаны в красной звездочке, линейной с зеленой линией, квадратичной в синем, полиномиальной в черном, экспоненциальной в розовом и логарифмическом графике в зеленом цвете с буквами О.Из остатков должно быть ясно, какая функция лучше всего подходит для ваших данных.