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

koolcoy

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



嘿嘿, 我那个同学今年又要参加baidu的算法大赛了, 上次就是来北京总部的...他特别牛.....一直搞算法的

给了你个鲜花, 哈哈...

我不太喜欢算法大赛, 感觉很无聊. 并且只有很少的公司会自己做算法. 实际的软件开发对算法需求都不大, 只要程序员心里对算法, 时间复杂度, 空间复杂度有个大概的数就行了.

Edengundam

原帖由 福瑞哈哥 于 2007-7-5 21:40 发表


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

比较两端缩小范围, 可以优化一下, 就是看看A的子友好最后一个ID和B的父好友的第一个ID的大小关系, 如果是小于等于就直接出结果.
其它情况就可以不考虑了, 算法的复杂度大于意义了, 很可能性能下降. 如果真的需要, 可以考虑对数据进行数据统计再着手进行.



我现在期待的是还有没有更好的点子...... 实在想不出什么了...在想我也无法冲破这些时间界了 估计高手还有高招
当然分析一下在2GB内存情况, 对于第一种思路和第二种思路, 性能的优劣可能相当的有挑战, 对于这种情况下, 第二种思路就要精心设计一下缓存策略了

福瑞哈哥

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


首先, 我们澄清, 搜索命中好友的概率只有万分之2.5
对于你的思路1W次平均的搜索总开销:
2.5 * ((1 + 2500) * 2500/2) + 9997.5 * 2500 = 32809375
对于后者开销:
2.5 * ((1 + 100) * 100 /2) + 9997.5 ...

建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

Edengundam

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

我不太喜欢算法大赛, 感觉很无聊. 并且只有很少的公司会自己做算法. 实际的软件开发对算法需求都不大, 只要程序员心里对算法, 时间复杂度, 空间复杂度有个大概的数就行了.

我那个同学挺猛, 一年到头一直比赛......今年还去了东京参加比赛...不过貌似总是和奖金失之交臂...

算法这东西我觉得是兴趣吧, 我算法就特别烂...
我觉得算法好还是有优势, 一些大公司还是有不少对算法要求很高的工作职位.

koolcoy

原帖由 福瑞哈哥 于 2007-7-5 21:46 发表


建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

比较集合就两种吧, 复杂度分别为O(m+n)和O(m*ln(n)), 先估算一下哪种快, 然后就用那种方法.

Edengundam

原帖由 福瑞哈哥 于 2007-7-5 21:46 发表


建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

typedef struct FriendList { int fc; int fl[50]; } FriendList; int com(FriendList *a, FriendList *b) {     int ac = a->fc;     int bc = b->fc;     if (ac == 0 || bc == 0)         return -1;     if (a->fl[ac - 1] < b->fl[0])         return -1;     if (a->fl[ac - 1] == b->fl[0])         return b->fl[0];     while (ac >= 0 && bc >= 0)         if (a->fl[ac] > b->fl[bc])             ac--;         else if (a->fl[ac] > b->fl[bc])             bc--;         else             return a->fl[ac];     return -1; }

如果需要返回多个结果, 再传进来结构体就行了..很简单的思路

哈哈, 刚才少写了个return.....

[ 本帖最后由 Edengundam 于 2007-7-5 23:03 编辑 ]

福瑞哈哥

原帖由 Edengundam 于 2007-7-5 22:03 发表



typedef struct FriendList {
int fc;
int fl[50];
} FriendList;


int com(FriendList *a, FriendList *b)
{
    int ac = a->fc;
    int bc = b->fc;
    if (ac == 0 || bc == 0)
       ...

学习。有序集合的交集。

robin10

if (a->fl[ac - 1] = b->fl[0])
        return b->fl[0];

Edengundam 大哥你少写了一个=吧。。。。

Edengundam

原帖由 robin10 于 2007-7-5 22:57 发表
if (a->fl[ac - 1] = b->fl[0])
        return b->fl[0];

Edengundam 大哥你少写了一个=吧。。。。

最近果然脑袋不行了...丢三落四....开始还少写个return ...

谢谢提醒.

O(m + n) 和 O (m * log(n))的情况大概是n/m > 8 的时候二分搜索就会更快了.

就是求解m + n > m * log(n)不等式...然后我转换求m + n == m * log(n) 表达式的解, 两边求导, 找驻点什么的...高数忘光了...然后大概得到了n = m^2/(m - 1) ....数学高手帮帮算算...

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)

*/