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

福瑞哈哥

每个用户是排序数组，用户id就是数组索引。
用户好友用排序数组，初始长度50，以后根据情况realloc扩充。
查找就简单了，定位用户A，遍历A的好友，af1,af2,...,afn，
再查找afx的好友看有没有B。完成。
内存也就使用几百M。
内存可能不止这么多，麻烦。

[ 本帖最后由 福瑞哈哥 于 2007-7-5 17:36 编辑 ]

福瑞哈哥

原帖由 feiyang21687 于 2007-7-5 17:13 发表
这样算法的时间复杂度O(n^2)，太慢了。

如果能放在内存中，如果你能做到比这还快，还干嘛去百度做题啊？
如果不嫌罗嗦，就使用双向指针吧。每个用户把视自己为朋友的用户也列出来。不过我是不会这么做的。

啊，双向指针也并不快。

[ 本帖最后由 福瑞哈哥 于 2007-7-5 17:30 编辑 ]

福瑞哈哥

原帖由 ivhb 于 2007-7-5 17:24 发表



用qsort+bsearch，怎么得出的那个复杂度？

同意，好友是顺序遍历是N，间接好友查找就不需要N了。
我觉得设计有一点是不能把非重要或者非常用功能当作优化重点。

福瑞哈哥

原帖由 converse 于 2007-7-5 17:27 发表
福瑞的算法,最坏的情况下要把某ID的所有好友的好友都给查一遍的.

没错，不过不是O(N^2)。

福瑞哈哥

原帖由 spibit 于 2007-7-5 17:55 发表
typedef struct _user
{
  int userid;

  // 好友数目
  int count;

  // 好友列表数组，最后一个为0表示结束。
  int *friends;
}user_t;

// user_t指针的数组，假设数据已经全部读进来了，use ...

我支持你。          因为这也是我的想法。

福瑞哈哥

原帖由 Edengundam 于 2007-7-5 19:11 发表



这个想法最直接. 其实给出的复杂度是总用户的复杂度, 既然使用了数组下标索引, 也就没有什么时间复杂度的问题.

这题关键是数据结构占用的内存数量. 以及每次查找A, B关系的时间开销.

这种直接的方法 ...

对，内存大概要2G，这是麻烦的地方。不过你知道搜索引擎公司都是怎么做的吗？ 如果一台机器放不下，那就用两台，把数据一分为二。或者一台机器两个进程，内存现在一般都是2G的，如果多进程可以把内存加到更多比如16G。

福瑞哈哥

原帖由 Edengundam 于 2007-7-5 20:26 发表



我意思是应该提高查找二维好友速度...空间换时间

关注，愿闻其详。

福瑞哈哥

原帖由 Edengundam 于 2007-7-5 21:12 发表



bingo

和我想的一样

帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB

因为每 ...

做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不见得有多少优势了。

确实会快一些，不过每次都要维护这两个有序数组也挺麻烦的。

福瑞哈哥

原帖由 koolcoy 于 2007-7-5 21:28 发表

怎么能够只比较两端就可以了呢?

如果只是要找他们是否有关系，只比较两端就可以了。

福瑞哈哥

原帖由 koolcoy 于 2007-7-5 21:35 发表

不行吧, 例如两个数组(1, 3, 5), (2, 3, 6), 只比较两端行吗?

你理解的是正确的，比较两端缩小范围后再比较。这也正是反向索引后能优化的地方。