Измерение расстояния для алгоритмов

Question

В настоящее время я работаю над проектом, в котором мне нужно количественно оценить (dis) сходство между алгоритмами - то есть, у меня есть несколько десятков алгоритмов, которые используются для этой же цели, и я хотел бы определите, какие из них наиболее близки (то есть более похожи) к другим, и которые действительно «новы».

Как мой Google-Fu, так и мой SO-Jutsu подвели меня, поэтому я был бы признателен, если бы кто-нибудь мог пролить свет на это. Существует ли такая метрика?

Answer 1

Как один из показателей сходства, вы можете создать набор данных n, несколько разумно сконструированных, а затем запустить каждый из ваших алгоритмов на всех этих наборах данных. Затем вы получаете n -мерный вектор времени выполнения, связанный с каждым алгоритмом, который затем можно удалять по любому старому расстоянию. Я бы предположил, что что-то вроде косинусного расстояния было бы хорошим предположением, поскольку, если ваши наборы данных имеют различные размеры, вы бы хотели классифицировать свои алгоритмы так, как они масштабируются. В дополнение к времени выполнения вы можете контролировать максимальное использование памяти или все, что вы можете придумать для измерения.