创造算法的算法:分治法

作者: 溪石iOS | 来源:发表于2019-01-22 22:48 被阅读12次

    有多少人学习算法时,都是从排序入手,然后就没有然后了,不是算法有多难,而是算法对程序员来说,有点类似武侠世界里的内功心法,练了半天,总觉得与功夫招式没什么大关系,和工作遇到的问题关系也不是那么直接,实际上,基本上所有语言都内置了排序的方法,有多少人会自己写个快排去排序的?!
    那么学习算法到底有什么用呢?这里我提供一个角度:

    学习算法是为了用程序的思想,抽象实际问题,提供方便的解决方案。

    分治法是编程界排名前5的重要算法之一,但是它本身并不是一种具体的算法,也没有典型的数据结构,我们先从一个例子来看下它能解决什么样的问题:
    《最大子序和》:
    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。


    分治法.001

    问题中,最终的结果当然是9个数字中的最大值,问题是,9个数字的子数组有多少呢?可以2两个一组、3个一组,4个一组,这样写算法必然繁琐复杂,要想办法简化一下问题,先把9个数字分成两部分:


    分治法.002

    假设我们已经求出了[-2...-5]部分的最大值,记为sumMax(0...7),问题就简单了,只需在sumMax(0...7)、4、sumMax(0...7)+4 三者之间取最大值即可。

    剩下的你可能已经知道了,[-2...-5]部分也需要求最大和,一样分为两部分,这样一直分下去:


    分治法.003

    最后会发现,只剩下 -2 和 1,这时,只需要比较 (-2 + 1)和 1 的大小,显然取1,这是为了满足题目中“连续子数组”的要求,靠右边的数代表所在组,才能参与更大分组的计算。

    由分析可见,用递归可以很方便的实现,只需要将去掉末尾的数组再次调用相同方法即可,由于取子数组很耗费计算时,这里展开为循环,下面完整算法(Swift描述):

    func maxSubArray(_ nums: [Int]) -> Int {
            var maxAll:Int = 0
            if (nums.count == 0) {
                maxAll = 0
                return 0
            }
            if (nums.count == 1) {
                maxAll = nums[0]
                return nums[0]
            }
            maxAll = nums[0]
            var subSumMax = 0
            if (nums.count >= 2) {
                for v in nums {
                    subSumMax += v
                    subSumMax = max(subSumMax, v)
                    maxAll = max(subSumMax, maxAll)
                }
            }
            return maxAll
        }
    

    maxAll 用来记录曾经达到过的最大和。
    通过以上的详细分析,可以总结出,分治法包括两个步骤:

    1. 将大问题分拆成小问题。
    2. 找到小问题的解决方案。

    以上过程是个互动过程,有时需要尝试不同的分拆方法,关键看分拆的小问题是否有一致的解决方案

    在众多算法中,很多都是分治法的具体实践:

    • 二分查找
    • 归并排序
    • 快速排序

    当你领悟了分治法的思想后,很多算法都可以自行推导得出,现在是不是对学好算法更有信心了呢?欢迎你的留言,我们一同修炼心法。

    相关文章

      网友评论

        本文标题:创造算法的算法:分治法

        本文链接:https://www.haomeiwen.com/subject/cmgrjqtx.html