Я тестирую алгоритм сортировки и пробовал его с разным объемом данных. 100 тысяч элементов 1 миллион элементов до 10 миллионов элементов.Как вычислить сложность алгоритма, имея время выполнения?
Мне нужно рассчитать сложность этого алгоритма, получив выходные данные о том, сколько времени прошло каждая сортировка.
Как я могу это сделать?
Пока вы не можете найти время работы алгоритма без математического анализа, эмпирические измерения могут дать вам разумное представление о том, как работает время работы алгоритма, или, скорее, программа --- ведет себя.
Например, если у вас есть n измерение (x1, y1), (x2, y2), ..., (xn, yn), где xi является размером входных данных и yi является временем программы на входе такого размера, то вы можете построить график функции, чтобы увидеть, является ли это многочлен. На практике это часто бывает. Тем не менее, трудно понять, что должен быть экспонентом из сюжета.
Чтобы найти экспонента, вы можете найти наклон линии, которая наилучшим образом соответствует точкам (log xi, log yi). Это связано с тем, что если y=C*x^k+lower order terms, то, поскольку доминирует член C*x^k, мы ожидаем log y =~ k*log x + log C, то есть уравнение логарифма является линейным, когда «исходное» уравнение является многочленом. (Всякий раз, когда вы видите линейную функцию в log-log plot, ваше время работы полиномиально, наклон линии говорит вам степень полинома.)
Вот график квадратичной функции y(x)=x^2: 
А вот соответствующая логарифмическая участка: 
Мы можем видеть, что это линия с наклоном 2 (на практике вы бы вычислить это, используя, например, linear least squares). Это ожидается, потому что log y(x) = 2 * log(x).
Код я использовал:
x = 1:1:100;
y = x.^2;
plot(x, y);
plot(log(x), log(y));
На практике функция выглядит хаотичным и наклон может (или должен) быть использован только как правило, когда ничего не доступно.
Я предполагаю, что есть много других трюков, чтобы узнать о поведении программы из измерений времени работы. Я дам другим шанс поделиться своим опытом.
Вы действительно не можете, так как время может также зависеть от порядка ввода входных данных. –
Что делать, если бы у меня были шаги, которые программа выполняла для завершения сортировки каждый раз? Я имею в виду «примитивные» шаги. – motleycrue
Он по-прежнему зависит от данных, например. диапазон пузырьков варьируется от O (n), если данные сортируются по O (n^2), если данные отсортированы в обратном порядке. Вам нужно будет определить характер входных данных для всех ваших тестовых случаев, и даже тогда это только скажет вам сложность для этого конкретного случая. –