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

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

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

一、需求

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

二、简单分析

最基本的做法,是两两比对,可以区分出临时的最大值和最小值,再拿临时的最大值和最小值往后比较,有新的最值则更新。总的需要的比较次数是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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3690 【模板】Link Cut Tree (LCT)

870
来自专栏逸鹏说道

小白眼中的AI之~Numpy基础

引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)

11410
来自专栏小鹏的专栏

tf API 研读4:Inputs and Readers

tensorflow中数据的读入相关类或函数: 占位符(Placeholders) tf提供一种占位符操作,在执行时需要为其提供数据data。 操作 描...

39410
来自专栏瞎说开发那些事

RPA与Excel(DataTable)

方法: 直接调用invokeCode,入参为已定义好的DataTable,出参为去重后的DataTable,代码如下

762
来自专栏zingpLiu

python2.x之pyshp的使用

1416
来自专栏九彩拼盘的叨叨叨

学习纲要:ES6系列:箭头函数和对象方法简写

772
来自专栏海天一树

小朋友学C语言(33):三目运算符

三目运算符(ternary operator),又称条件运算符、三元运算符,是计算机语言(c,c++,java等)的重要组成部分。它是唯一有3个操作数的运算符。...

2706
来自专栏刘琰的专栏

Redis 容量评估模型

业务侧申请redis服务器资源时,需要事先对redis容量做一个大致评估,因此提出一个较精确的redis容量评估模型就显得很有必要。

1.2K0
来自专栏逸鹏说道

小白眼中的AI之~Numpy基础

引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)

934
来自专栏Python爬虫实战

numpy基础操作快速入门

由于numpy不是python自带库,需要自己下载安装(如果用的是Anaconda,则不需要再去下载numpy库,因为其自带python环境以及许多第三方pyt...

531

扫码关注云+社区