in reply to Re^2: True Brute Force Longest Common Sub Sequence
in thread True Brute Force Longest Common Sub Sequence

If you just want to use brute force then using a hash is really cheating as it is already the begining of optimisation.

Have another look. That claim just isn't true.

common still visits every single combination of inputs, so it's brute force. Said nasty embedded loops *are there* and the hash doesn't affect the complexity.

common uses a hash to remove dups, something that isn't even necessary. It actually slows things down, if anything.

Even with the optimized common, said nasty embedded loops *are there* overall and the using the optimized common doesn't affect the overall complexity.

Replies are listed 'Best First'.
Re^4: True Brute Force Longest Common Sub Sequence
by tachyon-II (Chaplain) on Nov 26, 2007 at 00:31 UTC
    Even with the optimized common, said nasty embedded loops *are there* overall and the using the optimized common doesn't affect the overall complexity.

    Actually in the optimised version there are no nested loops and the overall complexity is greatly reduced. The non-optimised version certainly has embedded loops but as you show in the optimised version there is not any need for them because you are using a hash.

[reply]

      I strongly disagree. Not only does the optimized common still requires the nested loops to find the LCS, worse/average O(N^2*M^2 + M+N + M+N) is still O(N^2*M^2).

[reply]
[d/l]

        You are of course free to strongly disagree, however it is a matter of fact. Don't take my word for it, insert a loop counter variable and check the results.

[reply]

In Section Seekers of Perl Wisdom