把 n 个元素等分为两组𝐴1和𝐴2分别求这两组的最大值和最小值然后分别 将这两组的最大值和最小值相比较求出全部元素的最大值和最小值。如果 A1 和 A2 中的元素多于两个则再用上述方法各分为两个子集。直至子集中元素至 多两个元素为止。这是什么方法的思想?给出该方法的算法描述并分析其复杂 性不要代码
该方法的思想是分治法。
算法描述:
-
定义函数 find_max_min(nums),其中 nums 为待处理的元素列表。
-
若 nums 中元素个数不超过 2,则直接返回 nums 中的最大值和最小值。
-
将 nums 均分成两组 A1 和 A2。
-
分别对 A1 和 A2 调用 find_max_min 函数,得到它们的最大值和最小值。
-
将 A1 和 A2 的最大值和最小值进行比较,得到当前 nums 的最大值和最小值。
-
返回当前 nums 的最大值和最小值。
-
若 A1 和 A2 中的元素个数不超过 2,则直接返回它们的最大值和最小值。
-
对 A1 和 A2 递归调用 find_max_min 函数,得到它们的最大值和最小值。
-
将 A1 和 A2 的最大值和最小值进行比较,得到当前 nums 的最大值和最小值。
-
返回当前 nums 的最大值和最小值。
复杂性分析:
该算法的时间复杂度为 O(nlogn),其中 n 为元素个数。因为每次将元素均分为两组,所以分治树的深度为 logn,每层需要 O(n) 的时间复杂度来比较最大值和最小值。因此总时间复杂度为 O(nlogn)
原文地址: https://www.cveoy.top/t/topic/hegY 著作权归作者所有。请勿转载和采集!