有趣的算法(十一) ——分治法:快速​求最值

有趣的算法(十一)——分治法:快速求最值

(原创内容,转载请注明来源,谢谢)

一、需求

一个数组,里面有若干的数字,现需要得到这一组数字的最大值和最小值。

二、简单分析

最基本的做法,是两两比对,可以区分出临时的最大值和最小值,再拿临时的最大值和最小值往后比较,有新的最值则更新。总的需要的比较次数是2n-2。

三、优化

使用分治法快速求最值。即把数组分到最小的1-2个数,两两比较后,仅将最大值和最小值回传,再两两比较最值,回传新的最值,最终得出最大值和最小值。

分析需要比较的次数。当数组只有1个数时,T(1)=0;2个数时,T(2)=1。n个数字时,T(n)=2T(n/2)+2。

推导T(n)=2T(n/2)+2= 22T(n/22)+22+2…=2k-1T(2)+2k-1+2k-2+…22+2=2k-1+2k-2。

因此,当n=2k时,需要的次数是n/2+n-2=3n/2-2。当n不是2k,则次数会比3n/2-2略多,正好2的k次的数组长度时,这种算法较快。

四、实现

使用php编程,代码如下:

<?php
$x = 0;
//快速求最值-返回 array(min, max)
function quickMost(array $nums)
{
         $len = count($nums);
         if(1 == $len)
         {
                   returnarray(reset($nums), reset($nums));
         }
         if(2 == $len)
         {
                   $min =reset($nums);
                   $max =next($nums);
                   if($min >$max)
                   {
                            $tmp= $min;
                            $min= $max;
                            $max= $tmp;
                   }
                   $GLOBALS['x']++;
                   returnarray($min, $max);
         }
         $arr1 =array_slice($nums, floor($len/2));
         $arr2 =array_diff($nums, $arr1);
         list($min1, $max1) =quickMost($arr1);
         list($min2, $max2) =quickMost($arr2);
         $min = $min1 <=$min2 ? $min1 : $min2;
         $GLOBALS['x']++;
         $max = $max1 >=$max2 ? $max1 : $max2;
         $GLOBALS['x']++;
         return array($min,$max);
}
$testArr = array(7,8,5,1,4,9,0,3);
$res = quickMost($testArr);
var_dump($res);
echo $x;

结果如下:

aarray(2) { [0]=> int(1) [1]=> int(9) }
10

正确算出了最值,数字个数为8,则预测的比较次数为3n/2-2=3*8/2-2=10,和输出结果一致。

说明:

这里用到里一个php的array_diff,返回的是一个数组有的且另一个数组没有的数字,这样一定程度上如果有重复数字可以减少比较的次数。

但是,存在问题,当diff后,由于是返回一个差集,因此第二个数组可能是空树组的情况,例如输入的需要比较的数组为(1,1,1,1,1,1),此时的$arr2会是空树组,则会报错。因此,需要在第二次递归调用quickMost方法时,进行一个判断,即可正确解决此问题。修改如下:

         if(false == empty($arr2))
         {
                   list($min2, $max2) =quickMost($arr2);
                   $min = $min <= $min2 ?$min : $min2;
                   $GLOBALS['x']++;
                   $max = $max >= $max2 ?$max : $max2;
                   $GLOBALS['x']++;
         }

——written by linhxx 2018.01.18

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

1879
来自专栏有趣的Python

6-玩转数据结构-二分搜索树

电脑中的文件夹就是一种树结构,计算机中让人们使用的存储结构来源于生活。图书馆分区,分类,分子类。

852
来自专栏有趣的Python

9-C++远征之多态篇-学习笔记

使用父类指针指向子类对象,子类与父类有同名函数,加virtual成为虚函数,则调用相同的函数名的时候调用的是子类的函数。 不添加的时候,使用父类指针指向的是父类...

812
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

38710
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

511
来自专栏java学习

重要通知!小编出新的Java练习题已经公布答案了!!!

一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是(D)。 A. import classpackage ...

3398
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

3234
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

3675
来自专栏Java爬坑系列

【Java入门提高篇】Day9 Java内部类——静态内部类

  今天来说说Java中的最后一种内部类——静态内部类   所谓的静态内部类,自然就是用static修饰的内部类,那用static修饰过后的内部类,跟一般的内部...

1916
来自专栏老马说编程

(51) 剖析EnumSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了EnumMap,本节介绍同样针对枚举类型的Set接口的实现类EnumSet。与EnumMap类似,之所以会有...

1847

扫描关注云+社区