设计一个最优算法来查找一n个元素数组中的最大值和最小值,已知一种需要比较2n次的方法,请给一个更优的算法。请特别注意优化时间复杂度的常数。给出该算法最坏情况下的比较次数和该算法的步骤描述。(不用写代码,不给出比较次数的不得分)

2 5 收藏


直接登录
最新评论
  • Kidd_X   2016/01/07

    对半比较,然后建一个大堆,一个小堆?

  • Clark Li 软件工程师 2016/01/09

    geekforgeeks看到过,可以做到1.5n次

  • tianxun   2016/01/09

    等答案

  • 王先生 学生 2016/01/09

    分析:已知的比较2n次的方法,显然是将每个元素和最大值、最小值各比一次,要减少比较次数,可以有多种优化方法:
    方法一:一个元素先和最大值比较,如果比最大值大,就不用再和最小值比较(或者先和最小值比较,如果比最小值小,就不用再和最大值比较),一般情况下,这种优化后的比较次数一定会少于2n
    方法二:将数组元素按两个,两个分组,组内两元素有序存放,之后最小值跟组内较小的值比较,最大值只需跟组内较大的值比较,这样每组的比较次数是3,共n/2组,总的时间复杂度是3n/2次。

  • 追几何寻 学生 2016/01/10

    利用快排分划思想,先通过一次比较快排讲数据分为两部分,最小值在前半部分,最大值在后半部分,然后在两部分里面找到最大,最小值就可以了。时间复杂度3n/2-2.