Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^5: Patience Sorting To Find Longest Increasing Subsequence

by demerphq (Chancellor)
on May 07, 2006 at 19:10 UTC ( #547923=note: print w/ replies, xml ) Need Help??


in reply to Re^4: Patience Sorting To Find Longest Increasing Subsequence
in thread Patience Sorting To Find Longest Increasing Subsequence

What is the "it" that is O(N log log N) time though?

From what I understand its both finding the LIS and doing the patience sort. Actually, if i understand things correctly the B&S algorithm actually finds all increasing sequences in O(N log log N).

Also I have an implementation of Patience sorting with backrefs for the LIS that I will post when I get a moment.

---
$world=~s/war/peace/g


Comment on Re^5: Patience Sorting To Find Longest Increasing Subsequence

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://547923]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (8)
As of 2014-08-21 23:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (144 votes), past polls