|
Algorithm Development Kit 1.0 |
||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
See:
Description
Class Summary | |
---|---|
LineSweep | Implementation using linkedList for lineState to show performance degradation as the size of the state increases. |
LinkedListLineState | Class that shows the performance degradation when the line state is stored using a linked list instead of an augmented, balanced binary tree. |
Defines the classes needed to implement the LineSweep algorithm using double-linked lists to store the LineState.
Following such an approach prevents LineSweep from achieve its O((n+k) log n) behavior because of the costs in updating the line state. One will not see the performance degradation until the size of the line state exceeds a lower threshold. This example is provided as a warning. Make sure that when choosing to implement an algorithm that you choose the proper data structures that will achieve that goal. No detail can be overlooked. In this case, the costs of maintaining the line state will force LineSweep (using these linked lists) to be O(n^2) at times.
|
Algorithm Development Kit 1.0 | ||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |