| algorithmic question [message #493411] |
Mon, 07 February 2011 16:05  |
pyscho
Messages: 134
Registered: December 2009
|
Senior Member |
|
|
If given a set of numbers and a number n, find if there are 2 numbers in the set that add up to n. (O(n lgn) time) is optimal, n^2 is the simple answer
any ideas?
|
|
|
|
| Re: algorithmic question [message #493471 is a reply to message #493411] |
Tue, 08 February 2011 05:05  |
rleishman
Messages: 3728
Registered: October 2005
Location: Melbourne, Australia
|
Senior Member |
|
|
CREATE TABLE NUMS (NUM NUMBER);
{populate NUMS}
SELECT A.NUM, B.NUM
FROM NUMS A
JOIN NUMS B
ON B.NUM = :N - A.NUM;
Unfortunately, this does not meet your requirement because it is O(n) (assuming it performed a hash join), which is better than O(n log n). To achieve O(n log n) you would have to artificially slow it down by performing an Indexed Nested Loop, thus:
CREATE INDEX NUMS_IX ON NUMS(NUM);
SELECT /*+ ORDERED USE_NL(B) INDEX(B) */ A.NUM, B.NUM
FROM NUMS A
JOIN NUMS B
ON B.NUM = :N - A.NUM;
Ross Leishman
|
|
|
|
] 
Blog
Search
Help
Members
Register
Login
Home
