专栏首页JavaJourney数据结构与算法(五)| 递归行为及其时间复杂度分析

数据结构与算法(五)| 递归行为及其时间复杂度分析

锲而舍之,朽木不折;锲而不舍,金石可镂。 ---荀子《劝学》

1. 从思想上理解递归

递归行为从大问题划分为同等结构的小问题着手,每个小问题都和上一级的大问题是同等结构,同等结构的小问题解决了之后所收集来的信息通过分析能够整合出大问题的返回值。

递归就是 「以大化小」 的解决思路。

2. 程序如何运行递归函数

从一个例子来理解递归。

求数组arr[L..R]中的最大值,怎么用递归方法实现。

1)将[L..R]范围分成左右两半。左:[L..Mid] 右:[Mid+1..R] 2)左部分求最大值,右部分求最大值 3) [L..R]范围上的最大值,是max{左部分最大值,右部分最大值}

注意:左部分求最大值,右部分求最大值 是个递归过程,当范围上只有一个数,就可以不用再递归了。

首先,我们把这个递归函数先写出来,然后分析递归函数在系统中是如何运行的。

public int process(int[] arr, int L, int R) {
    //base case
    if (L == R) {
        return arr[L];
    }
    int mid = (L + R) >> 1;
    //递归
    int leftMax = process(arr, L, mid);
    int rightMax = process(arr, mid + 1, R);
    return Math.max(lmax, rMax);
}

给定数组arr = {3, 7, 6, 8, 2, 4, 7, 9},

数组及其索引下标

要找到该数组的最大元素,就是要调用函数 「process(arr, 0, 7)」 ,执行步骤:

L = 0, R = 7,此时mid = (0 + 7) / 2 = 3,程序运行到第8行 「int leftMax = process(arr, L, mid);」 处时,程序好像又返回去执行了函数 「process(arr, 0, 3)」 ,那么它在系统中其实是暂时把之前运行的一些列 「中间信息暂存到系统栈」 中,此时栈结构:

L = 0,R = 3,此时mid = (0 + 3) / 2 = 1,程序由运行到 「int lMax = process(arr, L, mid);」 位置,即执行函数 「process(arr, 0, 1)」 ,此时又将这一步的中间结果压入系统栈:

L = 0,R = 1,此时mid = (0 + 1) / 2 = 0,程序执行 「int lMax = process(arr, L, mid);」 即执行函数 「process(arr, 0, 0)」 ,此时 L==R,返回arr[L],也就是arr[0]=3,此时系统栈情况:

这个时候,弹出系统栈顶,并记住此时的leftMax = 3。

此时的栈:

据此恢复递归函数的执行现场:

process(arr,0,1)
mid=0
leftMax=3
rightMax=process(arr,1,1)

虚线栈帧弹出,此时计算出了 「process(arr, 0, 1)」 即arr数组0 ~ 1上的最大值,第10行计算出了0~1上的最大值为7。

此时还原到上一次的递归函数执行现场:

process(arr,0,3)
mid=1
leftMax=process(arr,0,1)=7
rightMax=process(arr,2,3)

继续上述类似入栈步骤,每次入栈都记录程序执行的行数、中间变量等信息。

「TIP:」 递归函数执行过程中,系统帮我们把运行过程中的一些中间信息放到栈中,如果我们自己做一个栈,改成迭代行为,也是可以实现的。因此,「递归函数都可以改写成非递归函数。」

3. 递归函数调用图解

针对上述递归函数,后续我们可以这么画图模拟调用:

递归过程图

这就是递归调用的逻辑图。把调用的过程画出结构图是必须的,这有利于分析递归。

通过一个简单例题的分析得知,递归底层是利用系统栈来实现的。平时分析递归的时候,建议画出逻辑图来辅助分析递归行为。

4. 计算递归算法时间复杂度-Master公式

计算递归算法的时间复杂度可以用Master公式:

时间复杂度为形如

T(N) = aT(\frac{N}{b}) + O(N^d),其中a、b、d为常数

的递归函数,可以直接通过以下条件来确定时间复杂度:

如果 \log_ba < d,时间复杂度为 O(N^d)
如果 \log_ba >d, 时间复杂度为 O(N\log_ba)
如果 \log_ba == d, 时间复杂度为 O(N^d\log_ba)

针对本文一开始提出的求数组最大值问题,来根据Master公式分析一下其时间复杂度。

对于数组arr,假设有N个数据的规模,获取最大值的时间复杂度记为:

T(N)

根据代码,我们把它分为了左侧部分和右侧部分,其数据量分别为N / 2(即「子递归数据规模同等」),所以,左右两侧递归计算的时间复杂度分别为:

T(\frac{N}{2})

所以有:

T(N) = 2 T(\frac{N}{2}) + 计算max(leftMax,rightMax)的时间

该递归函数整体上还有一部分时间是计算 「leftMax」「rightMax」 的最大值的,这部分的时间复杂度为O(1),所以,该递归函数的时间复杂度就是:

T(N) = 2T(\frac{N}{2}) + O(1)

所以代入到时间复杂度公式,有:

\log_ba = \log_22 = 1
O(N^d) = O(1) =>d = 0

所以,得出以下条件

\log_ba >d

再所以,该递归函数的时间复杂度为:

O(N\log_ba) = O(N\log_22) = O(N)

「TIP:」 使用Master公式计算递归时间复杂度的前提:划分的子递归的规模是一样的,即 「同等规模的子递归」


首发公众号 「行百里er」 ,欢迎老铁们关注阅读指正。代码仓库 「GitHub」 https://github.com/xblzer/JavaJourney

文章分享自微信公众号:
行百里er

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:行百里er
原始发表时间:2021-06-24
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 分析时间与空间复杂度《三钻数据结构与算法笔记》

    学习任何一门知识的时候,我们需要分析清楚这门知识的核心是什么,从而在这个核心中我们可以得到什么。如果我们是盲目的吸收知识,其实很多知识我们都是在目前场景、工作、...

    三钻
  • AI_第一部分 数据结构与算法(2.时间与空间复杂度分析)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    python编程从入门到实践
  • 最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

    在二叉树结点结构中加一个指针域,使其指向层次遍历的下一个结点,特别地,每一层的最后一个结点为空。(Code)

    java架构师
  • 【数据结构 | 入门】 入坑篇 (浙江大学数据结构学习笔记)

    类别分细,查找方便,但管理麻烦,同样,类别分粗一点,查找麻烦,管理方便 所以综上所述, 数据结构的组织方式决定了方式的效率

    计算机魔术师
  • 剑指 offer 面试题精选图解 10-I.斐波那契数列

    大家好,我是程序员吴师兄,欢迎来到图解剑指 Offer 专栏,在这个专栏里我将和大家一起学习如何用合理的思维来思考、解题、写代码。

    五分钟学算法
  • 码农也要学算法

    当“人工智能”、“AlphaGo”、“无人驾驶”、“智能投顾”等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算机通过提供给人类每天要面临的...

    前端教程
  • 理解算法的复杂度

    在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表示,不包括这个函数的低阶和首项系数,使用这种方式时,时间的复杂度...

    我是攻城师
  • 数据结构算法的时间复杂度_数据结构中排序的时间复杂度

    大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说数据结构算法的时间复杂度_数据结构中排序的时间复杂度,希望能够帮助大家进步!!!

    Java架构师必看
  • 前端学数据结构与算法(一):不会复杂度分析,算法等于白学

    兜兜转转了这么久,数据结构与算法始终是逃不过命题。曾几何时,前端学习数据结构与算法,想必会被认为不务正业,但现今想必大家已有耳闻与经历,面试遇到链表、树、爬楼梯...

    飞跃疯人院
  • 佩奇学编程 | 复杂度分析原来这么简单

    -------------------------------------------

    小小詹同学
  • 02 复杂度分析_pythoner学习数据结构与算法系列

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度...

    诡途
  • 数据结构与算法之基本概念

    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中...

    bigsai
  • 数据结构与算法学习笔记

    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏 。有不懂的地方指出来,我做修改。

    全栈程序员站长
  • 当今世界最为经典的十大算法 博客分类: 经典文章转载 算法数据结构网络应用数据挖掘J#

    本文转载自July CSDN博客:http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

    chroya
  • 数据结构与算法 (Kotlin语言描述)

    1.Kotlin 概述 为什么用Kotlin? Kotlin快速入门 2.数据结构与算法基础 时间复杂度 空间复杂度 递归函数 3.数组 4.栈...

    一个会写诗的程序员
  • 剑指Offer(第二版)面试题目分析与实现-面试需要的基础知识

    保持更新,转载请注明出处;更多内容请关注cnblogs.com/xuyaowen;

    xuyaowen
  • 坚持刷题678天的感受!

    刷题的原因各种各样,结合本人和朋友的经历,以及网上大家的分享,比较有代表性的原因有以下四种:

    Datawhale
  • PHP数据结构(二十二) ——快速排序

    PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行...

    用户1327360
  • 最大子序列和问题之算法优化

    Spark学习技巧

扫码关注腾讯云开发者

领取腾讯云代金券