算法的距离度量方式

Question

算法的距离度量方式

5

我目前正在一个项目中工作，需要量化算法之间的（不）相似性。也就是说，我有几十个用于同一目的的算法，我想量化哪些算法更接近（即更相似），哪些是真正的“新颖”。我的谷歌搜索和stackoverflow搜索都没有找到相关信息，所以我希望有人能提供一些帮助。是否存在这样的度量标准？

- Felipe Campelo

Google-Fu和SO-Jitsu哈哈。如果我们能根据问题中的双关语给予点赞就好了。 - user3235832

将它们初步分类为绝对指标，如运行时间和内存复杂度，是否表明类似的算法看起来很接近？ - Jongware

1

在遗传编程中，有通过小突变进化程序的概念——通常情况下，如果有小突变的概念，那么就会有距离的概念，因此值得研究一些遗传编程的研究（尽管这是关于程序而不是算法）。请参见https://en.wikipedia.org/wiki/Genetic_programming。 - John Coleman

谢谢大家。我打算使用运行时和内存复杂度作为次要证据来验证基于算法之间距离（无论是什么）的推断。@JohnColeman，从GP借鉴思想的想法很有趣。既然我首先要将所有算法表达为一个通用框架/标准化实现，那么可能可以使用一些GP的概念。这是一个冒险，但也是一个开始。 - Felipe Campelo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- George · Accepted Answer

作为一种相似性度量，您可以创建一些智能构建的数据集，并在所有这些数据集上运行每个算法。然后，您将获得与每个算法相关联的运行时间的n维向量，然后可以使用任意距离来衡量它们之间的相似性。我想像余弦距离会是一个不错的第一猜测，因为如果您的数据集大小各异，您可能会按照它们扩展的方式对算法进行分类。除了运行时间外，您还可以监视最大内存使用量或其他任何您可以想到的度量。