算法设计与分析习题谁会做给定数组A=(98,31,22,44,37,9)试用分治法求其第二小元素(要

网友回答

这个是利用分治思想来解
考点是快排可以用二分法对原数组进行排序
快排(QuickSort)是一种基于分治思想的二分排序法.对于一段序列,我们先
选出一个划分元素,然后用线性的时间复杂度将大于和小于划分元素的元素
移动到划分元素的两边,再由划分元素处将序列拆分为两部分,分别进一步
处理.显然这里划分元素的选择决定了拆分序列的平均程度.
因为算法是二分的,每段序列的处理是线性的,易知时间复杂度为O(nlgn).
可是假设每一次选择的划分元素都是序列里最大或最小的,那么拆分的时间
复杂度也会变成线性的,所以快排在最坏情况下的时间复杂度为O(N^2).