非平衡分治术和一个最优算法──兼论用分治术设计算法的基本原则

本文讨论了非平衡分治术，对一个分类问题（求极大元和极小元问题）用非平衡分治术给出 了一个最优算法．从理论和实例两方面说明：非平衡的分治术不容忽视，采用它常得到时间复杂 性为多项式阶的有效算法．本文接着对平衡的分治术进行了讨论，指出平衡不是主要的，要求 问题的大小“成倍地”减小才是基本的。最后得出了用分治术设计算法的一个基本原则。