rei*_*ost 6 algorithm similarity metric time-complexity
我有大量的对象,我需要弄清楚它们之间的相似之处.
确切地说:给定两个对象,我可以将它们的不相似性计算为数字,度量 - 较高的值表示较少的相似性,0表示对象具有相同的内容.计算此数字的成本与较小对象的大小成比例(每个对象具有给定大小).
在给定对象的情况下,我需要能够快速找到与它类似的对象集.
确切地说:我需要生成一个数据结构,将任何对象o映射到对象集合,与o不同,对于某些不相似度值d,这样列出集合中的对象不会花费更多时间.在数组或链表中(也许它们实际上是).通常,该集合将远小于对象的总数,因此执行此计算确实是值得的.如果数据结构假定为固定的d,那么它就足够了,但如果它适用于任意d,那就更好了.
你以前见过这个问题,还是类似的问题？什么是好的解决方案？
确切地说:一个直接的解决方案涉及计算所有对象之间的不相似性,但这很慢 - O(n 2)其中n是对象的数量.是否存在复杂性较低的通用解决方案？
在不了解该指标的更多细节的情况下，很难说。我没有任何消除 O(n^2) 方面的想法，但可能有一种方法可以减少涉及的一些常数。例如，如果您有欧几里得度量 d(p,q) = sqrt( (p_1-q_1)^2 + ..+ (p_n-q_n)^2)，您可以对距离 d 进行平方并将其与部分距离进行比较(p_i-q_i)^2 的总和，并在超过 d^2 时停止。
这是否真的会节省您的时间取决于仅计算被加数的比较的成本以及您可以通过这样做避免多少次被加数计算（显然，d 越小越好）。