一道百度试题，大家来试试

xi_qh

long i,j;
#define N 10000000
long id[N];
while(i=0;i<N;i++)
       id[N]=i;
/*
read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........
*/

/*
开始判断某个id是否二级好友
count=0;
while(j=id;j!=id[j];j=id[j])
        count++;
if(count==2)
        找到一个二级好友
*/

空间复杂度是N，时间复杂度是初始化O(N)+要搜索的好友数*2

robin10

read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........

不是很明白。。。

robin10

对比上面提到的两种算法，如果考虑最坏情况的话，是不是有这样的关系呢。。。？
对于第二种情况：假使A的好友有500，而加B的好友有1000W，那么查找B是不是A的2维好友的话，是不是要对比 500*（1000W-1）次呢？
而对于第一种情况，最坏的似乎是 在500个好友里面，对500个ID（假使A的500个好友里面每一个都有500个好友。。）的一次折半查找。。。。。具体不太清楚那一个时间多一点。。没有具体想。。。

robin10

而题目说。平均好友只有50。。。这样第一次会不会好点。。。

Edengundam

原帖由 robin10 于 2007-7-6 01:41 发表
对比上面提到的两种算法，如果考虑最坏情况的话，是不是有这样的关系呢。。。？
对于第二种情况：假使A的好友有500，而加B的好友有1000W，那么查找B是不是A的2维好友的话，是不是要对比 500*（1000W-1）次呢？ ...

******
但是因为保存父好友可能存在一种极端情况, 导致某个数组元素(n)相对另一个数组(m)非常大. (n >> m)
这种情况下可以考虑使用复杂度为m*log(n)的算法.
用m的每个元素去n中进行binary search.
******这个特例的搜索优化是同学想到的...

这个极端我需要的次数拖同学算法的福为:
500 * log(10M) < 4900

即使没有优化我需要的复杂度也只有10M + 500.

PS: 第一种才是500 * 10M

之前分析少了关键一步...每次都必须用一次binary search处理A, B是一维好友的情况. 第一种, 第二种情况开销都大约是6次(log50).
相比A,B二维关系, 貌似影响是可忽略的, 而且复杂度开销也是个线性的. 两个结论还是: N^2和min(m+n, m*log(n)).


[ 本帖最后由 Edengundam 于 2007-7-6 08:02 编辑 ]

titansword2000

我认为福瑞哈哥谈到下面的这种方法可能是最合适的(无论从时间还是从空间角度)：
取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不见得有多少优势了。

但就象koolcoy所说的那样，不能只比较两端。另外，算法在得到那个反向有序集合后还可以继续进行优化，因为它也是一个有序数组。

xi_qh

不好意思，漏掉一段
/*
read_and_set();
读入用户A的好友列表，并设置，比如假设用户A的id是0，好友是3,5,7,67,78,3332
那么id[2]=0 id[4]=0........
然后再设置A好友的好友，比如如果好友3的好友是 10，100，那么id[9]=2,id[99]=2.......
*/

xi_qh

对上面的补充
假设有三个用户1，10，100，其中10是1的好友，100是10的好友
要找1的二级好友
那么首先id[10]=1，然后id[100]=10,
然后开始查找。因为找100的好友就是两步，首先看100的内容和其索引号是否相符，不等，就查找以其内容为索引的那个位置。
代码也就是
/*
开始判断某个id是否二级好友
count=0;
while(j=id;j!=id[j];j=id[j])
        count++;
if(count==2)
        找到一个二级好友
*/

Edengundam

xi_qh 你的数据结构是一维数组?
你能介绍下你的数据结构如何存储嘛??
因为你只给了一行的例子, 所以看不太明白

难道要用快速并集的策略??但是如何证明, 相互数据不会影响计算count数??

xi_qh

的确是一维数组，就是用快速并集，在《C算法》里面开篇就讲到了。
储存方式就是一个用户的好友，其对应的数组的内容都存储其id
比如用户id是1，其好友是2，3，4，那么id[2]=1,id[2]=1,id[4]=1,本身id[1]=1
如果用户2的好友是5，6 那么id[5]=2,id[6]=2
现在开始查找 如果是用户7 ，因为id[7]=7,count=0,所以不是
用户6：id[6]=2,继续id[2]=1,继续id[1]=1,此时id和id[]内容相等，中止。count=2，找到一个。
关于相互影响的问题，再设置的时候，可以加一个判断，如果本身数组的内容已经是要找的id用户，此处是1，那就不要设置.