Алгоритм сложности асимптотного графа
Я готовлю проект C ++, в котором мне нужно вычислить сложность многих алгоритмов big-O и сравнить его с теоретическим значением на графике. Я сделал функцию времени, которая вычисляет время выполнения алгоритма, но я не нашел способа вычислить сложность и нарисовать кривую, используя время T и вход N.
Есть идеи ?
Решение
В двух словах: если вы определили теоретическую сложность T (n), все, что вам нужно сделать, это выполнить тест x раз для заданного диапазона n: n1, …, nx и измерить время каждого теста. Затем вы выбираете медиану нм из вашего набора n1, …, nx и вычисляете коэффициент c, определяемый как: c = t (нм) / T (нм). t (нм) — измеренное время для медианы n (нм), T (нм) — теоретическая сложность для нм.
Далее для каждого из ваших n вычислим коэффициент q, который является коэффициентом согласованности теоретической и экспериментальной сложности вашего алгоритма:
Наконец, вы можете нарисовать график q (n), который является асимптотическим графом, и он должен асимптотически сходиться к 1. Если ваш граф асимптотически опускается ниже 1, теоретическая сложность завышается, если выше 1 сложность недооценивается.
Другие решения
Других решений пока нет …