Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming
Bo Han, Yongquan Lu · 2012
The classical algorithm uses Dynamic Programming to construct an Optimal Binary Search Tree. In this paper, we research into the dynamical process of building an Optimal Binary Search Tree and present an optimized solution. Time complexity is reduced from O (n 3 ) to O (n 2 ). Meanwhile, three feasible parallel solutions are put forward to achieve greater optimization. Some experiments on cluster have been done to compare efficiency of parallel and serial algorithm and the result shows that the parallel algorithm is much better. In the case of a larger amount of testing data, the parallel solution can save half of the time consumption. However, because of the particularity of this issue, the parallel algorithm has its own limitation.