From: Arunachalam - view profile
Date: Mon, Apr 3 2006 3:47 pm
Email: Arunachalam <[EMAIL PROTECTED]>
Not yet rated
Rating:
show options
Reply | Reply to Author | Forward | Print | Individual Message | Show
original | Report Abuse | Find messages by this author
Here is the improvement to my previous algorithm.
Observation 1.
ax+by can appear in the solution only if ax+bj has appeared in
the
solution where j > y.
Observation 2.
ax+bn can be included only if a(x+1)+bn is included in the
answer.
1. Extract an+bn as the maximum
2. Form a heap with a(n-1)+b(n) and a(n)+b(n-1).
3. Extract the maximum from the heap ( assume max extracted is ai+bj )
4. Add ai+b(j-1) to the heap
5. Add a(i-1)+bn also to the heap if the extracted max is ai+bn.
So the worst case complexity for this log(n)+log(n-1)+..1.
The best case is O(n) where the heap will have only 2 elements.
PS: can someone prove using amortized analysis this solution has the
complexity of O(n).
This is of O(nlogn) as log(n!)= logn + log n-1 ... = Int logx = xlogx
-1or
it is sigma log(k*n-k) is maximum when k=n/2 so it is n/2 * log(n^2/4)
= >n logn
= O(nlogn)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
