回 帖 发 新 帖 刷新版面

主题:关于模糊比较,大家有什么好的算法没?我简单举个例子

我首先阐述一下,大致是怎么回事/

假如有这个一个数组:
     {1001,1002,1003,1004,1005,1006}

在下面这些数组群里,找出一个和这个数组最相识的数组
A:{2123,3245,3556,2389,9304,9850}
B:{1001,106,1003,1002, 1008,1000}
C:{3239,9485,9845,5865,2303,1454,4895}
D:{1001,10002,1003,1004,1005,1007}
E:{1001,10002,1003,1004,1005,1007,1008}
F:{1001,10002,1003,1004,1005,1007,1008,1009}

很自然D数组和需要比较的数组最相似。相识度达到 83.3%

如果一个个数字进行比较的话,需要的时间可能会比较长。

请问有没有比较好的算法来找出最合适的数组,最相似的数组?

注意两点:
1、比较中,与数组的顺序无关。如果有个数组是{1003,10001,1005,1004,1002,1006},那相似度是100%。与需要寻找的完全吻合

2、数字只是一个数字,把它们当作字符串来看。比如1003和1004的相似度为0%
1003和8437的相似度也是0%。1003只与1003是100%相似,其他的都不相似。

   谢先。如果有代码,最好是C/C++/C#  代码,其他是其他代码俺尽力看懂。 

回复列表 (共6个回复)

沙发

排序,一一比较

板凳

[quote]排序,一一比较[/quote]
我最初的想法也是这样,但发现这样效率比较低。
运算时间略长。。。

3 楼

假设数组长度为m,那么排序为mlog(m),n个数组的话,就是nmlog(m);

两个数组判断相似率的复杂度为m + m,n个数组判断就是2mn;

所以总复杂度为2mn + mnlog(m);

我不认为在无序的情况下还有更好的匹配算法。

4 楼

都是高手啊~~ 基础的偶我没怎么学好~~ 汗

5 楼

[quote]假设数组长度为m,那么排序为mlog(m),n个数组的话,就是nmlog(m);

两个数组判断相似率的复杂度为m + m,n个数组判断就是2mn;

所以总复杂度为2mn + mnlog(m);

我不认为在无序的情况下还有更好的匹配算法。[/quote]

假设数组长度为m,那么排序为mlog(m),n个数组的话,就是nmlog(m);
请问这个是什么概念?

6 楼

你不是说效率低吗?

我那是在分析算法复杂度。。

关于复杂度的分析法请参看数据结构的书。

我来回复

您尚未登录,请登录后再回复。点此登录或注册