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

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

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

一、需求

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

二、简单分析

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

相关文章

来自专栏大闲人柴毛毛

贪心算法(四)——最小代价生成树

问题描述 n个村庄间架设通信线路,每个村庄间的距离不同,如何架设最节省开销? 这个问题中,村庄可以抽象成节点,村庄之间的距离抽象成带权值的边,要求最节约...

5446
来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

1542
来自专栏WD学习记录

数据结构与算法2016-05-31

数据元素是数据的基本单位,在计算机程序中通常被作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是不可分割的、含有独立意义的最小数据单位,数据...

1022
来自专栏算法修养

LeetCode 126 Word Ladder II

具体的思路是,分别从起始和结束字符串出发两遍BFS, 得到每个点到起始字符串的最短距离和终点字符串的最短距离。 然后再从起始字符串出发,DFS 寻找路径。由于...

772
来自专栏用户2442861的专栏

最大的子序列和问题

http://blog.csdn.net/zhutulang/article/details/7505785

5391
来自专栏人工智能头条

70个NumPy练习:在Python下一举搞定机器学习矩阵运算

2152
来自专栏用户2442861的专栏

桶排序

http://blog.csdn.net/houapple/article/details/6480100

1844
来自专栏企鹅号快讯

Python排序(一)

“为了学习Python编程,通过Python编写了一些算法小程序,作为自己的学习笔记,同时分享给大家共同学习交流!” 现在计算机的广泛使用使得数据无处不在, 而...

1925
来自专栏desperate633

LintCode 恢复旋转排序数组题目分析代码

说明 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,...

792
来自专栏PHP在线

关于PHP浮点数精度损失问题

$f = 0.57; echo intval($f * 100); //56 结果可能有点出乎你的意外,PHP遵循IEEE 754双精度: 浮点数, 以64位...

2825

扫码关注云+社区