g*******y
发帖数: 1930 | 1 Google » Algorithm
Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
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(n^2)就没法提高了 | a**********s
发帖数: 588 | 2 Yes, I think:
Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
combination: the ith, jth and kth numbers (sorted from small to large).
You can essentially rule out 1/8 when you compare the required sum with that
of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
The total asymptotic cost is dominated by the sorting, which is O(NlgN).
up
【在 g*******y 的大作中提到】
: Google » Algorithm
: Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
: 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(n^2)就没法提高了
| g*******y
发帖数: 1930 | 3 好像是对的
挺好的方法啊，这么说来只要这个subset的元素个数是常数，都统一是nlogn的复杂度
不愧是传说中的牛人~
a
that
【在 a**********s 的大作中提到】
: Yes, I think:
: Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
: combination: the ith, jth and kth numbers (sorted from small to large).
: You can essentially rule out 1/8 when you compare the required sum with that
: of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
: The total asymptotic cost is dominated by the sorting, which is O(NlgN).
:
: up
| m********0
发帖数: 2717 | 4 我是来膜拜的。
a
that
【在 a**********s 的大作中提到】
: Yes, I think:
: Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
: combination: the ith, jth and kth numbers (sorted from small to large).
: You can essentially rule out 1/8 when you compare the required sum with that
: of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
: The total asymptotic cost is dominated by the sorting, which is O(NlgN).
:
: up
| Z**9
发帖数: 6 | 5 hi algorithmics,
有两个问题我不是很明白：
1. 每次去掉1/8后，剩下不是一个长方体，如何继续切分？
2. 如何保证选出来的i,j,k都两两不同？
a
that
【在 a**********s 的大作中提到】
: Yes, I think:
: Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
: combination: the ith, jth and kth numbers (sorted from small to large).
: You can essentially rule out 1/8 when you compare the required sum with that
: of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
: The total asymptotic cost is dominated by the sorting, which is O(NlgN).
:
: up
| M********G
发帖数: 1207 | | a**********s
发帖数: 588 | 7 1. After ruling out 1/8, you proceed by 7 subproblems each of scale N^3/8.
So
f(N^3) = 7*f(N^3/8)+O(1)
The total complexity is O(log_{8/7}N^3) = O(lgN)
2. Just forget about these cases :)
【在 Z**9 的大作中提到】
: hi algorithmics,
: 有两个问题我不是很明白：
: 1. 每次去掉1/8后，剩下不是一个长方体，如何继续切分？
: 2. 如何保证选出来的i,j,k都两两不同？
:
: a
: that
| f*********r
发帖数: 68 | 8 f(N^3) = 7*f(N^3/8)+O(1)
=> f(N^3) = O(N^3*log_8^{7}, not O(logN^3)
x-sum problems have a lower performance bound Omega(n^ceil(x/2)) for
comparison based method. so low bound for 3-sum is O(n^2), maybe google wants you to prove this results.
【在 a**********s 的大作中提到】
: 1. After ruling out 1/8, you proceed by 7 subproblems each of scale N^3/8.
: So
: f(N^3) = 7*f(N^3/8)+O(1)
: The total complexity is O(log_{8/7}N^3) = O(lgN)
: 2. Just forget about these cases :)
| Z**9
发帖数: 6 | 9 ye...I think so too...
O(N^3*log_8{7})..
wants you to prove this results.
【在 f*********r 的大作中提到】
: f(N^3) = 7*f(N^3/8)+O(1)
: => f(N^3) = O(N^3*log_8^{7}, not O(logN^3)
: x-sum problems have a lower performance bound Omega(n^ceil(x/2)) for
: comparison based method. so low bound for 3-sum is O(n^2), maybe google wants you to prove this results.
| a**********s
发帖数: 588 | 10 .... yeah, I realized I was wrong on the analysis part, and ruling out a corner isn't enough, hmm~~~
wants you to prove this results.
【在 f*********r 的大作中提到】
: f(N^3) = 7*f(N^3/8)+O(1)
: => f(N^3) = O(N^3*log_8^{7}, not O(logN^3)
: x-sum problems have a lower performance bound Omega(n^ceil(x/2)) for
: comparison based method. so low bound for 3-sum is O(n^2), maybe google wants you to prove this results.
| | | b***e
发帖数: 1419 | 11 Problematic. It is even hard to get the sum of 2 (for a sorted list) in
log(n). The minimum is O(n). I see your recursion is wrong. It should
be something like:
T(n) = 7 * T(n/2)
for a
that
【在 a**********s 的大作中提到】
: Yes, I think:
: Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
: combination: the ith, jth and kth numbers (sorted from small to large).
: You can essentially rule out 1/8 when you compare the required sum with that
: of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
: The total asymptotic cost is dominated by the sorting, which is O(NlgN).
:
: up
| a******h
发帖数: 19 | 12 Sorry, I never saw this in the book.
Could anyone explain how to get this O(N^3*log_8{7})
from f(N^3) = 7*f(N^3/8)+O(1)?
And what is the underscore after log? | f*********r
发帖数: 68 | 13 google master theorem or refer to Introduction to algorithms
【在 a******h 的大作中提到】
: Sorry, I never saw this in the book.
: Could anyone explain how to get this O(N^3*log_8{7})
: from f(N^3) = 7*f(N^3/8)+O(1)?
: And what is the underscore after log?
| a******h
发帖数: 19 | 14 Then what's the underscore? log_8{7} | f*********r
发帖数: 68 | 15 base-8 logorithm of 7
【在 a******h 的大作中提到】
: Then what's the underscore? log_8{7}
| g*******y
发帖数: 1930 | 16 I was thinking about the same flaw in algorithmics' solution. But I was not
courageous enough be to believe algorithmics was wrong. Hehe
By the way, where do you see a proof for Omega(n^ceil(x/2))? I might have
seen it somewhere for the Subset Sum NPC, but didn't know for sure.
wants you to prove this results.
【在 f*********r 的大作中提到】
: f(N^3) = 7*f(N^3/8)+O(1)
: => f(N^3) = O(N^3*log_8^{7}, not O(logN^3)
: x-sum problems have a lower performance bound Omega(n^ceil(x/2)) for
: comparison based method. so low bound for 3-sum is O(n^2), maybe google wants you to prove this results.
| f*********r
发帖数: 68 | 17 http://cjtcs.cs.uchicago.edu/articles/1999/8/cj99-08.pdf
not
【在 g*******y 的大作中提到】
: I was thinking about the same flaw in algorithmics' solution. But I was not
: courageous enough be to believe algorithmics was wrong. Hehe
: By the way, where do you see a proof for Omega(n^ceil(x/2))? I might have
: seen it somewhere for the Subset Sum NPC, but didn't know for sure.
:
: wants you to prove this results.
| w********p
发帖数: 948 | 18 本来觉得我的算法在nlgn和n^2之间，没在意
看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
得懂
assuming T=16
list after sorted
1, 2, 3, 6, 7, 8, 9
1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the las | s*****e
发帖数: 49 | 19 4)的"otherwise fail"不对吧。
return
【在 w********p 的大作中提到】
: 本来觉得我的算法在nlgn和n^2之间，没在意
: 看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
: 得懂
: assuming T=16
: list after sorted
: 1, 2, 3, 6, 7, 8, 9
: 1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
: 1)sort array
: 2)use two points point to start and end of the list....
: find the 2 elements in O(n)
| l*******g
发帖数: 4894 | 20 我觉得otherwise是对的阿,因为这个index不可能比number index大,如果这样就不可能
存在三个数的和是T了.这是1.
关键在于这个程序中开始从end取数, 然后做binarysearch, 也就是说对于array中1/3n
的数进行循环吧. 然后循环是binarysearch对于>2/3n的数来做的.还有一个递归.这个
复杂度能满足要求吗?
【在 s*****e 的大作中提到】
: 4)的"otherwise fail"不对吧。
:
: return
| | | d******n
发帖数: 122 | 21 3-sum hard one, O( n ^ 2)
1) sort O ( n lg n)
2) for each i, we check whether 2 item can sum up to T-a[i] ( O ( n ^ 2))
so total O ( n ^ 2 )
History
sum up
【在 g*******y 的大作中提到】
: Google » Algorithm
: Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
: 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(n^2)就没法提高了
| w********p
发帖数: 948 | 22 楼上的link 好像说最好可以到n^(3/2)
2）是可以优化的，因为是sorted list. 不过考虑的case有点多，懒得想了
【在 d******n 的大作中提到】
: 3-sum hard one, O( n ^ 2)
: 1) sort O ( n lg n)
: 2) for each i, we check whether 2 item can sum up to T-a[i] ( O ( n ^ 2))
: so total O ( n ^ 2 )
:
: History
: sum up
| w********p
发帖数: 948 | 23
1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the last 3 number , otherwise return
false;
2) pick up number from the end of the array,
Num=array[len-i-1]=9; i=0, numberIndex=le
【在 w********p 的大作中提到】
: 本来觉得我的算法在nlgn和n^2之间，没在意
: 看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
: 得懂
: assuming T=16
: list after sorted
: 1, 2, 3, 6, 7, 8, 9
: 1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
: 1)sort array
: 2)use two points point to start and end of the list....
: find the 2 elements in O(n)
| a**********s
发帖数: 588 | 24 Mine was very wrong, blush///
not
【在 g*******y 的大作中提到】
: I was thinking about the same flaw in algorithmics' solution. But I was not
: courageous enough be to believe algorithmics was wrong. Hehe
: By the way, where do you see a proof for Omega(n^ceil(x/2))? I might have
: seen it somewhere for the Subset Sum NPC, but didn't know for sure.
:
: wants you to prove this results.
|
|
