Я готовлю проект на C++, который я должен вычислить много сложностей алгоритмов big-O и сравнить его с теоретическим значением на графике. Я сделал функцию времени, которая вычисляет время выполнения алгоритма, но я не нашел способ вычислить сложность и нарисовать кривую с использованием времени T и ввода N.График асимптоты сложности алгоритма
Любые идеи?
В двух словах: если вы определили теоретическую сложность T (n), вам нужно выполнить проверку x раз для заданного диапазона n: n1, ..., nx и измерить время каждого теста. Затем вы выбираете медианный nm из вашего набора n1, ..., nx и вычислительного коэффициента c, определяемый как: c = t (nm)/T (nm). t (нм) измеренное время для медианы n (нм), T (нм) рассчитывается теоретическая сложность для нм. Далее, для каждого из вашего п, вычислите коэффициент д, который является коэффициентом согласованности теоретической и экспериментальной сложности вашего алгоритма:
Наконец, вы можете нарисовать график д (п), который является асимптотой графика и он должен сходиться асимптотически к 1. Если ваш график асимптотически опускается ниже 1, теоретическая сложность переоценивается, если выше 1 сложность недооценивается.
Ваша программа измеряет время для определенного значения n = n0. Где, как время работы, скажем, T = O (n) - график для n (= min_value до max_value). Если вы запустите свою программу для всех этих n (= min_value до max_value) и вычислите время для каждого входа, а затем график (ось y = время Vs x-axis = n), это должно быть похоже на график теоретической сложности (в этом случае T = O (n) имеет вид y = mx, где m является константой и влияет только на наклон линии, вы можете считать m = 1 для своих вычислений. – brokenfoot
Как сделать это с кодом на C++ ? –