程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

06 | 递归(下):分而治之,从归并排序到MapReduce

黄申 2018-12-21
你好,我是黄申。
上一节,我解释了如何使用递归,来处理迭代法中比较复杂的数值计算。说到这里,你可能会问了,有些迭代法并不是简单的数值计算,而要通过迭代的过程进行一定的操作,过程更加复杂,需要考虑很多中间数据的匹配或者保存。例如我们之前介绍的用二分查找进行数据匹配,或者我们今天将要介绍的归并排序中的数据排序等等。那么,这种情况下,还可以用递归吗?具体又该如何来实现呢?
我们可以先分析一下,这些看似很复杂的问题,是否可以简化为某些更小的、更简单的子问题来解决,这是一般思路。如果可以,那就意味着我们仍然可以使用递归的核心思想,将复杂的问题逐步简化成最基本的情况来求解。因此,今天我会从归并排序开始,延伸到多台机器的并行处理,详细讲讲递归思想在“分而治之”这个领域的应用。

归并排序中的分治思想

首先,我们来看,如何使用递归编程解决数字的排序问题。
对一堆杂乱无序的数字,按照从小到大或者从大到小的规则进行排序,这是计算机领域非常经典,也非常流行的问题。小到 Excel 电子表格,大到搜索引擎,都需要对一堆数字进行排序。因此,计算机领域的前辈们研究排序问题已经很多年了,也提出了许多优秀的算法,比如归并排序、快速排序、堆排序等等。其中,归并排序和快速排序都很好地体现了分治的思想,今天我来说说其中之一的归并排序(merge sort)。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(57)

  • Handongyang
    老师讲的是最经典的2路归并排序算法,时间复杂度是O(NlogN)。如果将数组分解成更多组(假设分成K组),是K路归并排序算法,当然是可以的,比如K=3时,是3路归并排序,依次类推。3路归并排序是经典的归并排序(路归并排序)的变体,通过递归树方法计算等式T(n)= 3T(n/3)+ O(n)可以得到3路归并排序的时间复杂度为O(NlogN),其中logN以3为底(不方便打出,只能这样描述)。尽管3路合并排序与2路相比,时间复杂度看起来比较少,但实际上花费的时间会变得更高,因为合并功能中的比较次数会增加。类似的问题还有二分查找比三分查找更受欢迎。

    作者回复: 很好的回答👍

    2018-12-21
    74
  • 大悲
    思考题:
    如果不是分为两组,而是多组是可行的,但是处理起来比较麻烦。虽然分组的时候,能够更快完成,但是在合并的时候需要同时比较多组中的数据,取最小的一个。当分组数量比较大的时候,在合并的时候,为了考虑效率,需要维护一个堆来取最小值。假设分为N组,分组的时间复杂度是logn(N为底), 合并的时候时间复杂度为nlogN,总的时间复杂度不变,还是nlogn。不知道理解对不对,请老师指教!

    作者回复: 用堆取最小值,思路不错

    2018-12-21
    15
  • swortect
    老师,如果要排序的数组很大,两个最大的子节点排好序之后,交给最终的机器做最后的排序依然是一堆数据放在一个机器上

    作者回复: 这里我有个细节没说清楚,如果数组是有序的,每次只需要从磁盘,有序的取出一部分到内存进行合并

    2018-12-24
    8
  • 永旭
    老师,你好
    归并排序代码中有非空判断代码
    if (a == null) a = new int[0];
    if (to_sort == null) return to_sort;
    什么情况下会出现数组是null??

    作者回复: 在这个例子里不会出现,不过在实际工作中,这个函数可能被其他代码调用,为了保险起见,加一个最基本的非法检测

    2019-01-04
    7
  • 会飞的猪
    python实现代码:
    def mergeSort(list):
        if(len(list)==0):
            return 0
        if(len(list)==1):
            return list[0]
        else:
            listHalfLen=int(len(list)/2)
            left=mergeSort(list[0:listHalfLen])
            right=mergeSort(list[listHalfLen:])
            data=merge(left,right)
            return data

    def merge(left,right):
        mid=[]
        ai=0
        bi=0
        if(isinstance(left,int)):
            leftLen=1
            left=[left]
        else:
            leftLen=len(left)
        if(isinstance(right,int)):
            rightLen=1
            right=[right]
        else:
            rightLen = len(right)
        while(ai < leftLen and bi < rightLen):
            if(left[ai]<right[bi]):
                mid.append(left[ai])
                ai+=1
            else:
                mid.append(right[bi])
                bi+=1
        if(ai< leftLen):
            newleft=left[ai:]
            for i in newleft:
                mid.append(i)
        else:
            newright = right[bi:]
            for i in newright:
                mid.append(i)
        return mid
    list=[3,8,5,9,7,1,10]
    mergeSort(list)
    刚学python,希望大家多多指教

    作者回复: 作为初学者,写得很不错👍

    2018-12-28
    7
  • 指间砂的宿命
    分成超过两个组的更多组是可行的,不过这样在递归调用时一个是有可能产生更多的中间状态数据,再一个在合并阶段,需要比较更多个分组的数据,实际上在最小粒度的时候,比较大小的就是两个数字,即便上层分成多个组,在合并的最底层依旧是从两两之间比较合并的,感觉分成多组的并没有啥优势,还带来了比较处理的复杂性

    作者回复: 是的 有读者说可以用堆来取多个组的最小值,虽然可行,但确实比较复杂

    2018-12-21
    7
  • Joe
    分成多组归并,主要是合并比较会比较麻烦,会在合并时增加复杂度。比如比较2个数大小,只需要1次,而比较3个数大小,最多需要3次。

    作者回复: 是的👍

    2019-01-08
    5
  • 子非
    递归层次太多了,堆栈会溢出

    作者回复: 是的 需要转换成循环 或者栈的数据结构

    2019-01-06
    4
  • 代码世界没有爱情
    # 切分
    def split_list(temp_list):
        if not isinstance(temp_list, list):
            raise TypeError
        else:
            if not temp_list:
                raise ValueError
            else:
                length = len(temp_list)
                if length == 1:
                    return temp_list
                import math
                left = math.ceil(length / 2)
                del math
                left_list = split_list(temp_list[:left])
                right_list = split_list(temp_list[left:])
                return merger_list(left_list, right_list)


    # 归并
    def merger_list(left, right):
        result = []
        while True:

            if left and right:
                left_0 = left[0]
                right_0 = right[0]
                if left_0 > right_0:
                    min_num = right.pop(0)
                else:
                    min_num = left.pop(0)
                result.append(min_num)
            elif left:
                result.append(left.pop(0))

            elif right:
                result.append(right.pop(0))
            else:
                break
        return result


    print(split_list([3, 1, 2, 7, 4, 6, 9, 9, 10, 11, 4, 5]))
    2018-12-29
    4
  • 有品味的混球
    MapReduce 分割,映射,洗牌,归约这几个步骤没有具体的例子,就感觉不是很明白,希望这几个步骤还是用文章前半部分的排序的例子来分别举例

    作者回复: 这个概念涉及了比较多分布式系统的设计,我可以在后面加餐内容放入一些,或者是放到实战篇内容补上

    2019-02-19
    3
  • Mr.J
    老师您好,归并这种,比如数组排序无限的对半分开,这样会不会性能反而不如对半分开到一定程度,剩下的用别的排序算法,应该有一个平衡点吧

    作者回复: 这是个好的想法,我觉得和实际数据的分布有关,不同的分布可以找到不同的平衡点,不过本身要测算数据的分布可能更耗时间。如果事先知道了数据的特点,应该是可以结合不同的排序来优化

    2018-12-24
    3
  • 逐风随想
    上学只上到初二,已经十几年没学习数学了。自从做了3年程序员,一碰到数学问题就头痛。
    2018-12-21
    3
  • 刘明
    和快排对比,虽然时间复杂度都是nlogN,但是归并排序的空间复杂度是O(n),快排则是原地排序。不过归并排序是稳定排序,快排则不是,两种各有优势。

    作者回复: 很好的比较

    2019-06-21
    1
    2
  • Ricky
    /*
     * 采用分而治之思想实现数组排序, 递归为其实现技巧
     */
    #include <iostream>

    using namespace std;

    void merge(int *array, int low, int mid, int high) {
        // left: low ~ mid, right: mid+1 ~ high
        int size = high - low + 1;
        int *tmp = new int[size];
        int i = low, j = mid+1, k = 0;
        while (i <= mid && j <= high) {
            if (array[i] <= array[j]) {
                tmp[k++] = array[i++];
            } else {
                tmp[k++] = array[j++];
            }
        }

        // the rest elements
        while (i <= mid) {
            tmp[k++] = array[i++];
        }
        while (j <= high) {
            tmp[k++] = array[j++];
        }

        // copy the elements to original array
        for (k = 0; k < size; ++k) {
            array[k+low] = tmp[k];
        }
    }

    void _mergeSort(int *array, int low, int high) {
        if (low >= high) return;
        int mid = low + ((high-low) >> 1);
        _mergeSort(array, low, mid);
        _mergeSort(array, mid+1, high);
        merge(array, low, mid, high);
    }

    void mergeSort(int *array, int size) {
        cout << "*****************before**************" << endl;
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
        _mergeSort(array, 0, size-1);
        cout << "*****************after**************" << endl;
        for (int i = 0; i < size; ++i) {
            cout << array[i] << " ";
        }
        cout << endl;
    }

    int main() {

        int array[] = {2, 3, 5, 1, 4, 9, 7, 6, 10};
        mergeSort(array, 9);

        return 0;
    }
    *****************before**************
    2 3 5 1 4 9 7 6 10
    *****************after**************
    1 2 3 4 5 6 7 9 10

    作者回复: 实现的思路很清晰,还用到了位移操作👌

    2019-01-09
    2
  • 叶嘉祺
    可以用数学方法证明二分归并排序是最优的应该。二分查找是可以证明的。

    二分法我是这样证明的: https://ghostbody.github.io/posts/algorithmn/prove-binary-search-is-better/

    对于归并排序我还在思考利用主定理进行证明。

    老师可以一起看下怎么证?

    作者回复: 第一次看到读者证明二分法是最优的,赞一个。至于归并排序应该是类似的,唯一不同的是,归并的合并过程也有一个复杂度要计算,而不是像比较大小那样O(1)

    2019-06-01
    1
  • 杰之7
    通过这一节的阅读学习,对归并排序算法有了理解。本质上就是二步,先分后和。而分开的过程中使用的分治的思想,实现分开中用递归的方法来实现。合并把函数结果返回。

    在大数据领域中,HDFS和MapReduce中都使用了这种分治的思想,把数据集划分给不同的机器,每台机器把数据分成许多块,Yarn调用程序让MR处理对应的数据,达到对海量数据的处理。

    目前需要做的就是理解之后花些时间实践,这样在原理的基础上更好的去理解。
    2019-02-13
    1
  • méng
    js 写的代码


    function guibingorder(arr) {

    if (arr.length > 1) {
    var leftarr = [];
    var rightarr = [];
    var splitindex = Math.floor(arr.length / 2);
    leftarr = arr.slice(0, splitindex);
    rightarr = arr.slice(splitindex, arr.length);

    leftarr = arguments.callee(leftarr);
    rightarr = arguments.callee(rightarr);

    var result = [];
    while (Math.max(leftarr.length, rightarr.length) > 0) {
    //右边遍历完了 或者 左边比右边的小,则 从左边取出来
    if (rightarr.length == 0 || leftarr[0] < rightarr[0]) {
    result.push(leftarr[0]);
    leftarr.splice(0, 1);
    } else {
    result.push(rightarr[0]);
    rightarr.splice(0, 1);
    }
    }

    return result;
    }
    return arr;
    }

    作者回复: 逻辑上很清晰

    2019-01-11
    1
    1
  • Jerry银银
    思考题:一分为二,是为了处理起来简单,这样也就有了更好的通用性;当然,分成很多也是可行的,但是在数学上,它们是等价的。这个问题类似于在算法领域只研究二叉树
    2019-01-01
    1
  • 代码世界没有爱情
    # python实现
    # 切分
    def split_list(temp_list):
        if not isinstance(temp_list, list):
            raise TypeError
        else:
            if not temp_list:
                raise ValueError
            else:
                length = len(temp_list)
                if length == 1:
                    return temp_list
                import math
                left = math.ceil(length / 2)
                del math
                left_list = split_list(temp_list[:left])
                right_list = split_list(temp_list[left:])
                return merger_list(left_list, right_list)


    # 归并
    def merger_list(left, right):
        result = []
        while True:

            if left and right:
                left_0 = left[0]
                right_0 = right[0]
                if left_0 > right_0:
                    min_num = right.pop(0)
                else:
                    min_num = left.pop(0)
                result.append(min_num)
            elif left:
                result.append(left.pop(0))

            elif right:
                result.append(right.pop(0))
            else:
                break
        return result


    print(split_list([3, 1, 2, 7, 4, 6, 9, 9, 10, 11, 4, 5]))

    作者回复: Python的实现 不错

    2018-12-29
    1
  • changchen
    哈哈 这个问题我记得当初公司宿舍聊过,分组多的话单从复杂度计算上是降低了,舍友(做硬件安全的)告诉我说是因为计算机是二级制的,底层处理上实际上多分组是效率低的。至今不明白其中的缘由,希望老师指点^^
    2018-12-24
    1
收起评论
57
返回
顶部