常见算法设计方法-分治法

分治法(Devide & Conquer)

1. 常见步骤

  • Devide 把一个问题的特殊实例划分成若干个子问题
  • Conquer 递归地解决每个子问题
  • Combine 将每个子问题的答案组合成最终答案

2. 举例分析

归并排序就是常见的一种采用“分治法”进行设计的算法,以下先给出具体的C#版代码示例

    /// <summary>
    ///     对列表进行递归排序
    /// </summary>
    /// <param name="list">待排序数组</param>
    /// <returns></returns>
    public static List<int> Sort(List<int> list)
    {
        if (list.Count <= 1)
            return list;
        var mid = list.Count/2;
        var left = new List<int>(); 
        var right = new List<int>(); 
        
        // Devide
        for (var i = 0; i < mid; i++)
            left.Add(list[i]);
        for (var j = mid; j < list.Count; j++)
            right.Add(list[j]);
        // Conquer
        left = Sort(left);
        right = Sort(right);

        // Combine
        return Merge(left, right);
    }

    /// <summary>
    ///     合并已经排序好的两个List
    /// </summary>
    /// <param name="left">Left List</param>
    /// <param name="right">Right List</param>
    /// <returns></returns>
    private static List<int> Merge(List<int> left, List<int> right)
    {
        var temp = new List<int>();
        while ((left.Count > 0) && (right.Count > 0))
        {
            if (left[0] <= right[0])
            {
                temp.Add(left[0]);
                left.RemoveAt(0);
            }
            else
            {
                temp.Add(right[0]);
                right.RemoveAt(0);
            }
        }

        if (left.Count > 0)
        {
            foreach (int item in left)
            {
                temp.Add(item);
            }
        }
            
        if (right.Count > 0)
        {
            foreach (int item in right)
            {
                temp.Add(item);
            }
        }
        
        return temp;

    }

分析这个算法可以发现,归并算法的递归部分在于不断地将待排序数组分为左右两个等长的数组直至左右列表中都只含有一个元素,再继续进行Merge操作,前者递归所花费的时间可以简单表示成2T(n/2),后者排序可以认为是θ(n),则总时间可以表示成T(n)=2T(n/2)+θ(n)。

平均情况下,定义的T(n)=输入规模为n之下时所有可能输入的期望时间,θ是渐进符号一种,大家可以简单认为对于输入n,f(n)存在精确上下界

接下来在计算时间复杂度的时候,针对这个优雅的时间函数我们可以有两种解决办法,第一种是判断整个递归树的长度和叶节点的个数,第二种则是直接套用主定理公式进行分析。这里我们采用第二种主定理进行分析。

这里是对主定理的相关说明

针对T(n)=aT(n/b)+f(n)的函数式子(a≥1,b>1),我们可以知道归并排序算法的函数符合主定理的第二种情况,即如果存在常数k ≥ 0,有 f(n)=θ(n^(㏒{b}a((㏒n)^k)),则有T(n)=θ(n^(㏒{b}a((㏒n)^(k+1)))。这里的k=0,则归并算法最终的时间复杂度T(n)=θ(n㏒n)

额外补充一个二分法实例

    /// <summary>
    ///     二分法查找
    /// </summary>
    /// <param name="list">传入的有序列表</param>
    /// <param name="beginIndex">起始位置</param>
    /// <param name="endIndex">终止位置</param>
    /// <param name="x">需要查找的x</param>
    /// <returns>返回的列表索引</returns>
    public static int BinarySearch(List<int> list, int beginIndex, int endIndex, int x)
    {
        if ((x > list.LastOrDefault()) | (x < list.FirstOrDefault()))
            return -1;

        if (x == list[beginIndex])
            return beginIndex;

        if (x == list[endIndex])
            return endIndex;

        var mid = (beginIndex + endIndex)/2;
        if (x == list[mid])
            return mid;
        return x > list[mid] ? BinarySearch(list, mid, endIndex, x) : BinarySearch(list, beginIndex, mid, x);

    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每周一算:Move Zeros

思路:创建一个临时数组nonZeroElements,遍历nums,将nums中非0元素赋值到nonZeroElements中,而后按顺序将nonZeroEle...

1082
来自专栏从零开始学 Web 前端

05 - JavaSE之数组

1454
来自专栏C语言及其他语言

【蓝桥杯系列】第一节 C的基本用法

置顶编程范收获更多热门编程快讯 大家好,最近很多小伙伴向我反应小编!我参加了蓝桥杯但是我连那是什么都不知道,我该怎么训练?是不是在网站刷题就可以啊? 在这里我要...

3887
来自专栏Python爬虫与算法进阶

Leetcode Solutions(一) two-sum

在map[整数]整数的序号中,可以查询到a的序号。这样就不用嵌套两个for循环了。

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

P2023 [AHOI2009]维护序列

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部...

28410
来自专栏从流域到海域

《笨办法学Python》 第4课手记

《笨办法学Python》 第4课手记 这节课目的是让你掌握变量,跟C语言非常类似,很简单。 左边是变量名用”=”号给变量赋值。 不同的是我没有看到变量声明,作者...

1838
来自专栏程序猿DD

第三章 正则表达式括号的作用

第三章 正则表达式括号的作用 不管哪门语言中都有括号。正则表达式也是一门语言,而括号的存在使这门语言更为强大。 对括号的使用是否得心应手,是衡量对正则的掌握水平...

2556
来自专栏云霄雨霁

排序----插入排序

1430
来自专栏desperate633

Python爬虫之正则表达式入门正则表达式语法正则表达式实例ReMatch对象贪婪匹配和最小匹配

Re库是Python的标准库,主要用于字符串匹配 调用方式: import re

661
来自专栏智能算法

Python学习(四)---- 列表生成式、生成器、迭代器和内置函数

https://blog.csdn.net/fgf00/article/details/52061971

902

扫码关注云+社区

领取腾讯云代金券