article · 2012
Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming
Cited by 5Open access
Abstract
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.
Cite this paper
Han, B., & Lu, Y. (2012). Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming. https://doi.org/10.2991/emeit.2012.45
Han, Bo, and Yongquan Lu. “Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming.” 2012, https://doi.org/10.2991/emeit.2012.45.
Han, Bo, and Yongquan Lu. 2012. “Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming.” https://doi.org/10.2991/emeit.2012.45.
Han, B. and Lu, Y. (2012) ‘Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming’. Available at: https://doi.org/10.2991/emeit.2012.45.
@article{han2012research,
title = {{Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming}},
author = {Han, Bo and Lu, Yongquan},
year = {2012},
doi = {10.2991/emeit.2012.45}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.