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

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 编辑 ]

Edengundam

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

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

Edengundam

原帖由 A.com 于 2007-7-6 10:07 发表

PS：由于A->X->B的好友关系可能是单向的，所以反向好友的算法都有可能存在疏漏，无法采用

这个你是指哪个算法??

反向的建立是简单, 因为输入数据有序了, 所以建立数据结构不会疏漏. 如下没写完的分配, 大意就是初始化过程和数据结构.

#define USER_NO 10000000 #define AVERAGE_NO 50 typedef struct FriendList { int    list[AVERAGE_NO]; } FriendList; typedef struct Friend { int    fc; FriendList    *fl; } Friend; typedef struct MapFriend { Friend *cf; Friend *pf; } MapFriend; MapFriend mapFriend[USER_NO]; void buildMapFriend(int id, int fcount, int *flist) {     Friend *tmp     mapFriend[id].cf->fc = fcount;     mapFriend[id].cf->fl = flist;     while (fcount--)     {         tmp = mapFriend[flist[fcount]].pf;         if (tmp->pf == NULL)         {             tmp->pf = (Friend *) malloc0(sizeof(Friend));             tmp->pf->fl = (FriendList *) malloc0(sizeof(FriendList));         }         tmp->pf->fl->list[tmp->pf->fc++] = id;         // if fc >= 50, we need to alloc another FriendList to Friend...^^     } }

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

Edengundam

原帖由 xi_qh 于 2007-7-6 09:46 发表
的确是一维数组，就是用快速并集，在《C算法》里面开篇就讲到了。
储存方式就是一个用户的好友，其对应的数组的内容都存储其id
比如用户id是1，其好友是2，3，4，那么id[2]=1,id[2]=1,id[4]=1,本身id[1]=1
如 ...

比如下面这个列表:
1          3,5,7,9
2          1,3,5,9
3          4,5,8,9
5          1,2,39
9          1,3

数据结构是一次把所有信息存储上??
初始化过程                   数组索引-->
     |
     |
    \/
数组索引                          [1]    [2]     [3]   [4]    [5]    [6]  [7]   [8]   [9]
初始化值                   1      2       3      4      5      6     7      8     9
读入id=1用户信息          1      2        1     4       1      6    1       8     1
读入id=2用户信息          ?      2         ?     4       ?      6    ?       8     ?


这个数据结构是怎么变化的...不太理解你最后一句话的意思.
是每次查询时候, 都需要进行一次初始化嘛???

Edengundam

原帖由 xi_qh 于 2007-7-6 10:42 发表
的确这是个问题，在查询某个用户的好友时，需要初始化，但是只需初始化某一个id的好友和好友的好友

这样内存占用小, 但是对数组初始化(10,000,000)相对50来说开销就不划算了.
另外, 一个用户id平均需要7个数字字符(假设是ASCII编码的文件, 每个字符占用1字节)分隔符是一个\t
平均好友列表50 * (7+1): 7表示用户id: 1表示逗号和最后的换行. 平均每行的长度: 8 * 51 = 408字节.
408 * 10M = 4GB
这样下来, 对于磁盘性能貌似是很大的挑战. :wink: