three sum复杂度nlg(n)怎么解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

three sum复杂度nlg(n)怎么解

three sum复杂度nlg(n)怎么解# JobHunting - 待字闺中

P*y2013-03-14 07:03

1 楼

刚W家电面的，先给了O(n^2)的，然后问nlg(n)的解法，
提示用hash_map，想不出来，大伙想想，咋解?

b*u2013-03-14 07:03

2 楼

w家是哪家？
排序以后做

P*y2013-03-14 07:03

3 楼

w...lab
是three sum，不是two sum

【在 b*****u 的大作中提到】

: w家是哪家？
: 排序以后做

r*e2013-03-14 07:03

4 楼

3SUM目前简单形式的最优解就是O(n^2)
看来你被面试官忽悠了
http://en.wikipedia.org/wiki/3SUM

【在 P*******y 的大作中提到】

: 刚W家电面的，先给了O(n^2)的，然后问nlg(n)的解法，
: 提示用hash_map，想不出来，大伙想想，咋解?

P*y2013-03-14 07:03

5 楼

wiki上3SUM-hardness是不是说已经证明了最少只有O(n^2)解，对吧？
可能真被忽悠了。看我前面写太快让我来点思考这个问题。。。
不过刚通知过了，进入下一轮电面。他家要两轮哎

【在 r*******e 的大作中提到】

: 3SUM目前简单形式的最优解就是O(n^2)
: 看来你被面试官忽悠了
: http://en.wikipedia.org/wiki/3SUM

r*e2013-03-14 07:03

6 楼

赞，加油

【在 P*******y 的大作中提到】

: wiki上3SUM-hardness是不是说已经证明了最少只有O(n^2)解，对吧？
: 可能真被忽悠了。看我前面写太快让我来点思考这个问题。。。
: 不过刚通知过了，进入下一轮电面。他家要两轮哎

f*e2013-03-14 07:03

7 楼

什么背景？

【在 P*******y 的大作中提到】

: 刚W家电面的，先给了O(n^2)的，然后问nlg(n)的解法，
: 提示用hash_map，想不出来，大伙想想，咋解?

d*x2013-03-14 07:03

8 楼

你就是被忽悠了
算法分析课上说了，我们至今不知道k-sum有没有优于O(n^(k-1))的解。。

【在 P*******y 的大作中提到】

P*y2013-03-14 07:03

9 楼

cs fresh PhD

【在 f*****e 的大作中提到】

: 什么背景？

P*y2013-03-14 07:03

10 楼

算法课四年前上的已经还给老师了

【在 d**********x 的大作中提到】

: 你就是被忽悠了
: 算法分析课上说了，我们至今不知道k-sum有没有优于O(n^(k-1))的解。。

r*h2013-03-14 07:03

11 楼

g4g上面提到了一个4sum的O(n^2 log n)的解
http://www.geeksforgeeks.org/find-four-elements-that-sum-to-a-g
存下每一对可能的2sum，O(N^2)时间，然后给这些pair之和排序，耗时O(N^2 log N^2)
=> O(N^2 log N)，最后在这些pair之中找2um，耗时O(N^2)。

【在 d**********x 的大作中提到】

: 你就是被忽悠了
: 算法分析课上说了，我们至今不知道k-sum有没有优于O(n^(k-1))的解。。