|
||||
Title: Sum-of-pair score of an array faster than O(n^2) Post by Conga on Feb 29th, 2012, 5:51am Assume you have an array (I1, I2, ...., In) of characters (C1, C2,...., Cr) and a scoring function between such characters s(Ix, Iy). There are n*(n-1)/2 possible comparisons and a simple all-against-all sum-of-pair algorithm could easily be done in O(n^2). Now....assuming you have the counted numbers of each character within the array (#C1, #C2,...., #Cr). Is it possible to get the sum-of-pair score faster than O(n^2), maybe even O(n)? Thanks a lot for the help! |
||||
Title: Re: Sum-of-pair score of an array faster than O(n^ Post by william wu on Mar 9th, 2012, 6:21pm I am assuming that the scoring function is symmetric, which is implied by the statement that there are C(N,2) possible comparisons. Here is a start, although I'm guessing it is not smart enough to meet what is desired. The runtime is O(r^2); more precisely, r*(r-1)/2 + r log r, where the latter summand is due to sorting the histogram. Code:
Sample output: data={7, 0, 8, 2, 1, 5, 8, 0, 6, 7, 2, 1, 0, 6, 1, 2, 8, 6, 5, 5, 8, 4, 5, 9, 0, 6, 0, 0, 9, 3} hist=[3, 1}, {4, 1}, {7, 2}, {9, 2}, {1, 3}, {2, 3}, {5, 4}, {6, 4}, {8, 4}, {0, 6] sum//N = 23200 which matches the brute-force all pairs number: Code:
|
||||
Title: Re: Sum-of-pair score of an array faster than O(n^ Post by Conga on Mar 14th, 2012, 9:25am Hey William, thanks a lot for the reply! You are correctly assuming that the scoring function is symmetric. I was suspecting that it can be done in O(r^2) using binomials, but so far I was not able wrap my head around it. Not sure if it is possible in O(n), but your approach is already something that will help me a lot! Thanks a lot! Conga |
||||
Title: Re: Sum-of-pair score of an array faster than O(n^ Post by towr on Mar 14th, 2012, 9:48am You can't do better than O(r^2) in the worst case, because the score for every distinct pair of characters may be distinct, and so you need to use all r*(r-1)/2 of them in the worst case. |
||||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |