A Selection Problem for Management Based on Divide and Conquer Algorithm
Xiaohui Wang, Yong Zhang, Hongyan Zhao · 2009
Selection problem, which is to find the kth smallest element in a sequence of n numbers in arbitrary order, is a typical problem in algorithm design and analysis. The select problem is solved by divide and conquer algorithm. The general algorithm is given, and the complexity of this algorithm is analyzed and discussed. The divide and conquer algorithms are related to backfitting and Markov chain Monte Carlo techniques, which divide the problem in a divide and conquer strategy into smaller pieces. Confidence intervals taking model uncertainty into account are based on the bootstrap in combination with MCMC techniques.