这是分治法的思想。该方法的算法描述如下:

  1. 将n个元素等分为两组A1和A2。
  2. 分别求出A1和A2的最大值和最小值。
  3. 比较A1和A2的最大值和最小值,求出全部元素的最大值和最小值。
  4. 如果A1和A2中的元素多于两个,则对A1和A2分别执行上述步骤,直至子集中元素至多两个为止。

该算法的时间复杂度为O(nlogn),因为每次分组时需要对n个元素进行一次分割,而分割的次数为logn,故时间复杂度为O(nlogn)。

把 n 个元素等分为两组𝐴1和𝐴2分别求这两组的最大值和最小值然后分别
将这两组的最大值和最小值相比较求出全部元素的最大值和最小值。如果 A1
和 A2 中的元素多于两个则再用上述方法各分为两个子集。直至子集中元素至
多两个元素为止。这是什么方法的思想?给出该方法的算法描述要筒述并分析其复杂
性不要代码

原文地址: http://www.cveoy.top/t/topic/heg4 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录