实在书荒了，打算看看中原五白的 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>paladin - 谈古论金，黄梁一梦

实在书荒了，打算看看中原五白的

实在书荒了，打算看看中原五白的# paladin - 谈古论金，黄梁一梦

H*M2014-02-03 08:02

1 楼

given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想不出什么天外飞仙的算法达到O(nlgn)
谁有点idea?

f*g2014-02-03 08:02

2 楼

我吃西红柿
天蚕土豆
唐家三少
辰东
梦入神机
以前看过jj的，感觉it已经入魔了，没兴趣了
其他四位都是起点的小白大神，一直没敢碰，有啥书可以打发书荒的么？
多谢啊

h*e2014-02-03 08:02

3 楼

你听错题了吧

up

【在 H*M 的大作中提到】

: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想不出什么天外飞仙的算法达到O(nlgn)
: 谁有点idea?

G*s2014-02-03 08:02

4 楼

沦落到五白的书的时候，
还不如整点别的事做

n*r2014-02-03 08:02

5 楼

答案是没有这样的算法

up

【在 H*M 的大作中提到】

: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想不出什么天外飞仙的算法达到O(nlgn)
: 谁有点idea?

t*t2014-02-03 08:02

6 楼

中原五白，番茄最白？

H*M2014-02-03 08:02

7 楼

是在别地方烤来的.
那最快的算法是多少?

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

: 你听错题了吧
:
: up

R*n2014-02-03 08:02

8 楼

唐三的斗罗大陆还可以，虽然胡煽情滥起腻，情节和设定有独到之处。
逆苍天的杀神可看，可以给众多蜂拥而上的小白作者当模板教材。

c*g2014-02-03 08:02

9 楼

easy to get n^2, not sure about nlogn

【在 H*M 的大作中提到】

: 是在别地方烤来的.
: 那最快的算法是多少?

w*p2014-02-03 08:02

10 楼

我也见过这道题。我相信我的算法是nlgn, 但是有些细节不知道怎么写成sudocode

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

: 你听错题了吧
:
: up

H*M2014-02-03 08:02

11 楼

你说说吧
据说无解?

【在 w********p 的大作中提到】

: 我也见过这道题。我相信我的算法是nlgn, 但是有些细节不知道怎么写成sudocode

m*02014-02-03 08:02

12 楼

O(n^2) is trivial .
貌似前段时间Quant版讨论过，有人给出paper link
目前的最好算法就是 O(nlogn)。
记不太清楚了。找了半天没找到。

up

【在 H*M 的大作中提到】

: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想不出什么天外飞仙的算法达到O(nlgn)
: 谁有点idea?

g*y2014-02-03 08:02

13 楼

本版就讨论过，我发的帖子问的。
结论是不可能，结论是有paper证明的！！！

g*y2014-02-03 08:02

14 楼

本版就讨论过，我发的帖子问的。
结论是不可能，结论是有paper证明的！！！

h*e2014-02-03 08:02

15 楼

找不到就对了，因为3SUM目前没有人知道o(n^2)的算法，只有在一些特定的model下有
稍微快一点的。

【在 m********0 的大作中提到】

: O(n^2) is trivial .
: 貌似前段时间Quant版讨论过，有人给出paper link
: 目前的最好算法就是 O(nlogn)。
: 记不太清楚了。找了半天没找到。
:
: up

H*M2014-02-03 08:02

16 楼

ft..我说在哪见过..
那如果是两个,是不是就是hash后,直接过一遍?还是有什么天外飞仙的方法?

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

: 本版就讨论过，我发的帖子问的。
: 结论是不可能，结论是有paper证明的！！！

m*02014-02-03 08:02

17 楼

那就是我记错了。
一个类似的题目在quant版讨论过，
比这个题目复杂。

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

: 找不到就对了，因为3SUM目前没有人知道o(n^2)的算法，只有在一些特定的model下有
: 稍微快一点的。

m*02014-02-03 08:02

18 楼

link to the paper?

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

: 本版就讨论过，我发的帖子问的。
: 结论是不可能，结论是有paper证明的！！！

g*y2014-02-03 08:02

19 楼

忘了，记得是篇会议文，还记得貌似是Fairylander给的link

【在 m********0 的大作中提到】

: link to the paper?

l*i2014-02-03 08:02

20 楼

wikipedia search 3SUM problem. There is no better solution than O(n^2)
currently and there are a number of problems that would have a faster
solution if 3SUM has a better than O(n^2) solution, say O(nlogn).