一个google intern的面试题

ArXoR

原帖由 softsongs 于 12/15/06 11:06 发表
a1....an, 一共有n个元素，任意两个元素相乘，有n(n-1)/2 个结果，
想要找出最大的ak , 使得ak = ai* aj, 并且， i != j != k; 那么至少我们需要遍历一遍 这n(n-1)/2 个结果，因为每一个结果都有可能是我们要找的 ...

可能结论是对的，但是论证方法不对。
而且o和O不是一个概念。。。o(f(n))和O(f(n))不一样的

按这个方法我们讨论一下单源最短路问题，不妨限制在完全无向图G，|G|＝n里，给定源点s
G共有n个节点，任意从s出发的简单路有(n-1)!条，共有(n-1)!个结果
想要找到最短的简单路，那么我们至少要遍历一遍这(n-1)!个结果，因为每个结果都有可能是我们要找的。。。
所以完全无向图上单源最短路问题复杂度至少O((n-1)!)?

明显是不对的，如果要证明复杂度下界，一个可能容易一点的间接的方法就是把其他问题复杂度下界已经证明的问题规约到这个上，产生矛盾才行，比如基于比较的排序算法复杂度复杂度下界是O(nlogn).

对于这个问题。。。至少我还没想到怎么证明其下界是O(n^2).

Please correct me if I'm wrong.

ArXoR

原帖由 Edengundam 于 12/14/06 10:47 发表
我比较笨...只找到了o(n^2)的办法...

建立2颗 AVL 树. 一颗是这个整数集合的, 一棵是2个数的乘积. 计算时候遇到ai == 1 || aj == 1 || ai == aj就不存储乘积了.
建立之后, o(1) 时间取得两颗树的最大值进行 ...

基于二叉搜索树的操作复杂度都是O(logn)的，怎么在O(1)内完成？
难道可以O(n)建一棵树，然后O(n)完成最大值的输出？
这样我们就可以找到一个基于比较的排序算法复杂度是O(n)了，这是不可能的，因为其下界已经证明了是O(nlogn)

你的复杂度应该是O(n^2 * logn)

ArXoR

原帖由 Edengundam 于 12/15/06 12:13 发表



确实是我说错了, 我实际是想用 heap (抱歉我记成AVL....了). 这样我能保证取最值是O(1).

。。。还是不行，取完最值还得维护堆性质。。。还要O(logn)...^_^

ArXoR

原帖由 crspo 于 12/17/06 11:32 发表
[code]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void inline swap(int *x,int *y)
{
  int tmp;
  tmp=*x;
  *x=*y;
  *y=tmp;
}


void max_heapify(int a ...

hash表就好了，不用最内层的二分，省掉O(logn)

ArXoR

原帖由 crspo 于 12/17/06 11:32 发表
[code]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void inline swap(int *x,int *y)
{
  int tmp;
  tmp=*x;
  *x=*y;
  *y=tmp;
}


void max_heapify(int a ...

而且只是复杂度期望是O(n^(3/2))，不是理论最坏界
开方不一定能到达sqrt(n)
比如
2,2^2,2^4,2^8...