首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在每次迭代中产生n- (i + 2)个函数调用的递归函数的时间复杂度是多少?

在每次迭代中产生n-(i+2)个函数调用的递归函数的时间复杂度是O(n!),即阶乘时间复杂度。

递归函数的时间复杂度可以通过递归的深度和每次递归的时间复杂度来计算。在这个问题中,每次迭代产生的函数调用数量是递减的,即每次迭代中产生的函数调用数量为n-(i+2)个。

假设每次递归的时间复杂度为O(1),那么每次迭代的时间复杂度为O(n-(i+2))。由于每次迭代的时间复杂度是递减的,所以总的时间复杂度可以表示为:

O(n-2) + O(n-3) + ... + O(1)

根据等差数列求和公式,上述表达式可以简化为:

O(n(n-1)/2)

进一步简化为:

O(n^2)

因此,每次迭代中产生n-(i+2)个函数调用的递归函数的时间复杂度是O(n^2)。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

青蛙跳台阶

关于斐波那契数列递归求解期间复杂度我们简化其求解过程,按照如下方式求解。 递归时间复杂度是:递归次数*每次递归中执行基本操作次数。所以时间复杂度是: O(2^n) 。...5.2 空间复杂度 每一次递归都需要开辟函数栈空间,递归算法空间复杂度是: 递归深度N*每次递归所要辅助空间 如果每次递归所需辅助空间是常数,则递归空间复杂度是 O(N)。...因为上面的递归实现,虽然每次递归都会有开辟两分支,按理说递归调用了 多少次,就开辟了多大栈空间,按照这个逻辑,那么空间复杂度时间复杂应该是一样, 都是 O(2^n) 。...6.迭代递归实现虽然简单易于理解,但是 O(2^n) 时间复杂度和 O(n) 空间却让人无法接受,下面采用迭代方式来实现,时间复杂度为 O(n),空间复杂度为 O(1)。...下面给出网友 beautyofmath 文章关于斐波那契数列三种解法及时间复杂度分析实现。

94720

青蛙跳台阶问题暨斐波那契数列

3.2空间复杂度 每一次递归都需要开辟函数栈空间,递归算法空间复杂度是: 递归深度N∗每次递归所要辅助空间 递归深度N*每次递归所要辅助空间 如果每次递归所需辅助空间是常数,则递归空间复杂度是...因为上面的递归实现,虽然每次递归都会有开辟两分支,按理说递归调用了 多少次,就开辟了多大栈空间,按照这个逻辑,那么空间复杂度时间复杂应该是一样, 都是O(2n)O(2^n)。...4.迭代实现 递归实现虽然简单易于理解,但是O(2n)O(2^n)时间复杂度和O(n)空间却让人无法接受,下面迭代具体实现,比较简单,就不再赘述实现步骤。...下面给出网友beautyofmath文章关于斐波那契数列三种解法及时间复杂度分析实现。...递归等式如下: image.png 6.2具体实现 递归等式是一2为公比等比数列,所以递归迭代实现起来都比较简单,参考如下: //递归法 //时间复杂度O(n),空间复杂度O(n) int

1K22
  • 【算法与数据结构】复杂度深度解析(超详解)

    时间复杂度概念 时间复杂度定义:计算机科学,算法时间复杂度是一函数,它定量描述了该算法运行时间。...2^N) 原因: 斐波那契数列递归定义是:Fib(N) = Fib(N-1) + Fib(N-2),每次调用Fib函数,它会递归调用自己两次。...可以看出每次递归产生两条子节点,形成一二叉树结构。...这里每次都分解成2子问题,所以时间复杂度是O(2^ N)。 Fib递归函数时间复杂度是指数级O(2^N),属于最坏情况下递归。...函数递归定义,每递归一次就会在函数调用push一栈帧,递归深度等于输入N,随着N增加而增加,每个栈帧中保存信息(如参数N值等)大小为常量,所以总栈空间大小就是递归深度N乘以每个栈帧大小,即

    19510

    一文学会排列组合

    时间复杂度是多少呢,从以上步骤其实可以看到是第四步做快排时时间复杂度,即 O(nlogn)。...,那用字典序法时间和空间复杂度是多少呢 由于全程只用了arr 数组,空间复杂度显示是 O(n) 而时间复杂度显然是第一步快排空间复杂度 + 持续做 next_permutation 计算时间复杂度...看起来字典序法比递归时间复杂度更高,所以我们应该使用倾向于使用递归吗?这里注意: 递归实现是通过调用函数本身,函数调用时候,每次调用时要做地址保存,参数传递等,这是通过一递归工作栈实现。...具体是每次调用函数本身要保存内容包括:局部变量、形参、调用函数地址、返回值。...所以时间复杂度差不多情况下,优化选择非递归实现方式 什么是组合 看完了排列,我们来看看组合,首先我们还是先看看组合定义 组合(combination)是一数学名词。

    1.2K20

    普通人如何理解递归算法

    当人们提到“递归”一词,不知道如何理解它,也有人会问递归迭代有什么区别?首先可以从定义上入手来分析,递归是自身调用自身函数进行循环、遇到满足终止条件情况时逐层返回来结束。...迭代则是函数内某段代码实现循环,循环代码参与运算变量同时是保存结果变量,当前保存结果作为下一次循环计算初始值。 如何实现递归算法设计方法?...""" 什么是递归函数存在着调用函数本身情况,这种现象就叫递归递归思想 加入1+2+3一直加到10,如何快速得到结果呢?...先去计算他时间复杂度假设时间复杂度为f(n)=2n+1, 那么f(n)计算方法第一行执行了一时间单位,第二行执行了n时间单位,第三行执行了n时间单位,可以得出f(n)=2n+1。...讲解递归时间复杂度时候,我们提到了递归算法时间复杂度本质上是要看: 递归次数 * 每次递归时间复杂度。 可以看出上面的代码每次递归都是O(1)操作。

    46511

    【初阶数据结构】——时间复杂度和空间复杂度详解(C描述)

    时间复杂度定义: 计算机科学,算法时间复杂度是一函数(注意这里说函数不是编程语言中函数,就是指数学我们学函数),它定量描述了该算法运行时间。...先给大家介绍一下这个函数吧。 这是一函数: 它就是字符串中去查找一字符,如果找到,返回该字符地址,如果找不到,返回空指针。 那它时间复杂度应该怎么算呢?...递归调用了几次呢? 是不是N次啊,Fac(N )要调用Fac(N - 1) ,Fac (N - 1)再调用Fac(N - 2) ,以此类推,直到Fac(1)结束。 那每次递归有几次运算呢?...那总次数其实就是一等差数列: N N-1 N-2 ... 3 2 1 求和就是N*(N+1)/2,那只保留最高阶,去掉系数,就是O(N^2) 所以,对于递归函数时间复杂度计算: 我们要算就是每次递归调用执行次数累加...这是我们计算时间复杂度是分析图,它递归调用了这么多次,但是,这么多分支,它们进行递归,开辟函数栈帧,是同时进行吗? 不是的。 它们是一分支,一分支按照先后顺序进行

    34010

    数据结构与算法:复杂度

    对于每个 N,函数只进行一次递归调用。因此,如果初始值为 N,那么会有 N 次递归调用。所以这个函数时间复杂度是 O(N)。...在这样递归调用,每增加一 N,递归层数加一,每一层结点数几乎是上一层两倍(除了接近底部,当 N 小于 3 时,不再继续拆分)。...因此,如果我们考虑每个函数调用是树节点,那么整个递归过程涉及节点总数(即函数调用总数)大约是一满二叉树节点数,这是因为除了最底层,几乎每个节点都会分裂成两个子节点。...递归调用: 冒泡排序是一迭代算法,不涉及递归调用,因此不会因为递归调用导致栈空间显著增加。 动态分配内存: 在此实现,没有动态分配内存;算法仅在原始数组上进行操作。...对于每个大于 0 N,都会产生递归调用,直到 N 降至 0。 由于递归调用会造成调用栈大小随 N 线性增长,因此 Fac 函数空间复杂度是 O(N)。

    12410

    数据结构之树(Topk问题, 链式二叉树)

    一.topk问题 取N个数中最大(小)前k值,N远大于k 这道题可以用堆方法来解决,首先取这N个数前k值,用它们建堆 时间复杂度O(k) 之后将剩余N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大...1.概念及应用场景 双路递归是一种算法思想,指的是递归过程同时处理两个子问题,从而提高递归效率和性能。...例如,归并排序,可以同时对左半部分和右半部分进行排序,然后将它们合并成一有序序列,从而实现排序目的。...处理一些问题时,双路递归比单路递归更有效率,例如在归并排序,双路递归可以同时对左半部分和右半部分进行排序,然后将它们合并成一有序序列,从而减少了排序时间复杂度。...双路递归空间复用是指在递归过程重复利用之前开辟空间,以减少内存使用量。以 longlong Fib(size_t N) 函数为例,该函数作用是计算斐波那契数列第 N 个数值。

    10110

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

    递归函数时间复杂度分析 如果一递归函数再每一次调用自身时,只是调用自己一次,那么它时间复杂度就是这段递归调用最大深度。...,因为每次调用都会截取字符串最后一位,所以这段程序递归调用次数就是递归深度,也就是字符串自身长度,也就是O(n),这也是递归最简单调用,每一次只调用自身一次;接下来我们使用递归求解斐波拉契数列...} 这个递归函数调用自身时,又调用了两次自身,那是不是说明这段递归函数时间复杂度是O(n²)?...我们可以看到,当要计算7时,需要计算出6和5;当要计算6和5时,又要分别计算出5和4以及4和3;每次这颗递归树展开叶子节点都是上一层两倍,也就说这是一指数级算法,时间复杂度为O(2ⁿ)。...最后 下面这段代码每次都会出队数组第一元素,那它时间复杂度是多少了?

    90700

    告别递归,从零开始一文学会递归解题

    什么是递归 简单地说,就是如果在函数存在着调用函数本身情况,这种现象就叫递归。...以阶乘函数为例,如下, factorial 函数存在着 factorial(n - 1) 调用,所以此函数递归函数 public int factorial(int n) { if (...(n) } return f(n-1) + f(n-2) } 那么改造后时间复杂度是多少呢,由于对每一计算过 f(n) 我们都保存了中间态 ,不存在重复计算问题,所以时间复杂度是...,按着函数功能来解释,递归问题其实很好解析,切忌每一子问题上层层展开死抠,这样这就陷入了递归陷阱,计算机都会栈溢出,何况人脑 4.时间复杂度分析 从第三步补充好函数我们可以推断出 f(n)...+ 2n-2 + ....+ 1 显然时间复杂度为 O(2n),很明显指数级别的时间复杂度是不能接受,汉诺塔非递归解法比较复杂,大家可以去网上搜一下 进阶题 现实中大厂很多递归题都不会用上面这些相对比较容易理解

    61710

    一文学会递归解题

    什么是递归 简单地说,就是如果在函数存在着调用函数本身情况,这种现象就叫递归。...以阶乘函数为例,如下, factorial 函数存在着 factorial(n - 1) 调用,所以此函数递归函数 public int factorial(int n) { if (...(n) } return f(n-1) + f(n-2) } 那么改造后时间复杂度是多少呢,由于对每一计算过 f(n) 我们都保存了中间态 ,不存在重复计算问题,所以时间复杂度是...,按着函数功能来解释,递归问题其实很好解析,切忌每一子问题上层层展开死抠,这样这就陷入了递归陷阱,计算机都会栈溢出,何况人脑 4.时间复杂度分析 从第三步补充好函数我们可以推断出 f(n)...+ 2n-2 + ....+ 1 显然时间复杂度为 O(2n),很明显指数级别的时间复杂度是不能接受,汉诺塔非递归解法比较复杂,大家可以去网上搜一下 进阶题 现实中大厂很多递归题都不会用上面这些相对比较容易理解

    44920

    《丢鸡蛋问题》重制版来袭~

    每次移动,你可以取一鸡蛋(如果你有完整鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。 你目标是确切地知道 F 是多少。...否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。如果它没碎,那么我们肯定知道 F = 2 。因此,最坏情况下我们需要移动 2 次以确定 F 是多少。...时间小时,一共三道题,分别是本题,合并 k 链表,以及种花问题。 这道题我很早时候做过,也写了题解[2]。现在看来,思路没有讲清楚。没有讲当时思考过程还原出来,导致大家看不太明白。...(图 4) 与其递归地进行这个过程,我们可以使用迭代方式。相比于上面的递归式,减少了栈开销。然而两者有着很多相似之处。 如果说递归是用函数调用来模拟所有情况, 那么动态规划就是用表来模拟。...空间复杂度:O(K * N) 总结 对于困难,先举几个简单例子帮助你思考。 递归迭代关系,以及如何从容地两者间穿梭。 如果你还不熟悉动态规划,可以先从递归做起。

    85910

    【基础算法】递归算法

    递归算法是一种直接或间接调用原算法算法,一使用函数自身给出定义函数被称为递归函数。利用递归算法可以将规模庞大问题拆分成规模较小问题,从而使问题简化。...无论是递归算法还是递归函数,最大特点都是“自己调用自己”。 斐波那契数列 斐波那契数列规律是:第一项是1,第二项是1,以后每一项都等于前两项之和。我们问题是:斐波那契数列第n项是多少?...就像上述fibonacci()函数,当n==1||n==2函数返回1,不再调用自己。如果一递归函数没有定义非递归初始值,那么该递归调用是无法结束,也就得不到结果。...虽然通过递归算法结构简单,已于理解和实现,但是由于需要反复调用自身,所以运行效率较低,时间复杂度和空间复杂度较高,使用时应考虑效率和性能问题。...使用循环取出当前数组每一元素,添加到临时结果数组每次递归调用只修改原数组数据,调用完perm()后需要将数组恢复到迭代状态。

    34710

    递归算法题练习(数计算、带备忘录递归、计算函数值)

    递归介绍 概念:递归是指函数直接或间接调用自身过程。 解释递归关键要素: 基本情况(递归终止条件):递归函数条件,当满足该条件时,递归终止,避免无限递归。...可以理解为直接解决极小规模问题方法。递归表达式(递归调用):递归函数语句,用于解决规模更小子问题再将子问题答案合并成为当前问题答案。...(常数小) 2.适用于问题规模没有明显缩减,或者需要特定迭代次数。(二元组) 3.适合处理大部分动态规划问题 部分情况下,递归和循环可以相互转化。...用一数组a记录下数字每一位上数字是多少,然后枚举当前位上数字,递归向下去求方案数并求和即可。...'; return 0; } (三、计算函数值) 用户登录 问题描述: 神秘世界,有一传说中神秘花园,被认为蕴藏着无限知识。

    13610

    超全递归技巧整理,这次一起拿下递归

    递归方式存在弊端 递归实现代码时,会遇到很多问题,比如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等问题。...函数调用耗时多、空间复杂度递归中会涉及到很多函数调用,当函数调用数量比较多时候,会使得耗时比较多。同时,由于调用一次就会在内核栈中保存一次现场数据,因此空间复杂度也会比较大。 1.4....归并排序 归并排序每次分解都是一分为二,整个递归过程画成递归树之后如图所示。m(n) 时间复杂度为 m(n/2) 时间复杂度乘以 2,加上合并所需要时间复杂度。...虽然具体时间复杂度无法求出,但是通过这个范围也可以知道全排列时间复杂度是很大。 ★ 上述例子,掌握递归求解方式才是最重要,不要纠结于精确时间复杂度是多少。...那么,递归树从根节点到树任意节点路径,都对应着某个时刻函数调用链组成堆栈。递归越深节点月靠近栈顶,也就越早返回。

    1.2K20

    谁能想到,求最值算法还能优化?

    max2 = nums[i]; } } return new int[] {max1, max2}; } 显然两算法时间复杂度都是 O(n),但如果我们以 if 判断次数作为算法效率评估标准...因此,算法 if else 比较次数为 2,总时间复杂度是多少呢?...这就涉及递归算法复杂度分析,设算法复杂度为 (n为递归函数处理元素个数,或者称为问题规模),那么可以得到如下公式: 其中 是因为 2 个子问题递归调用,每个子问题规模是原来 1/2;...如果你能明白这个递归关系(归纳假设),就有可能想到每次前进 2优化解法。...最后可以发现,通过f(n-2)去推断f(n)是最高效,写成迭代就是每次前进两步 for 循环,复杂度为: 对于动态规划问题也是一样,前文经常说对 dp 数组不同定义可以得到完全不同解法,这其实就是归纳假设

    82720

    数据结构 | 时间复杂度与空间复杂度

    ,关于时间&空间复杂度更多知识可以往下看 ---- 时间复杂度 先说概念 计算机科学,算法时间复杂度是一函数,它定量地描述了该算法运行时间 同大多数读者一样,我也不喜欢冗长复杂官方解释...,通俗来说,算法基本操作执行次数(循环部分),就是代表了该算法时间复杂度,比如下面这段代码 //请问这段代码时间复杂度是多少?...O(2 ^ N) 递归本来就是一很麻烦东西,更何况这是计算斐波那契数列 递归时间复杂度,计算每次递归中执行次数累加 我们可以将递归斐波那契数列水平展开,即 1+2+4+8+16+...,忘记了同学可以往上翻翻 当出现函数调用时,形参部分空间不计入空间复杂度计算,递归除外,递归会建立额外函数栈帧 函数运行时所需要栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了...先递出,再回归,如果中途遇到递归,继续递出,因此计算递归空间复杂度时,计算每次递归调用变量个数相加(所开辟空间),也可以看作递归深度 显然这里递归深度是 N,开辟了N栈帧,每个栈帧使用了常数个空间

    21610

    剑指offer | 面试题30:字符串排列

    : 初始化一 Set ,用于排除重复字符;将第 x 位字符与 i ∈ [x, len(c)] 字符分别交换,并进入下层递归; 剪枝: 若 c[i] Set ,代表其是重复字符,因此 “剪枝”...; 将 c[i] 加入 Set ,以便之后遇到重复字符时剪枝; 固定字符: 将字符 c[i] 和 c[x] 交换,即固定 c[i] 为当前位字符; 开启下层递归调用 dfs(x + 1) ,即开始固定第...复杂度分析: 时间复杂度0(N!N) :N为字符串s长度;时间复杂度和字符串排列方案数成线性关系,案数为N x(N- 1)x (N- 2)...x2x1,即复杂度为0(N!)...空间复杂度0(N2) :全排列递归深度为N,系统累计使用栈空间大小为0(N) ; 递归中辅助Set累计存储字符数量最多为N +(N- 1)+...+2+1=(N + 1)N/2 ,即占用O(N2)额外空间...,定义到函数之外,这样无需带到递归函数参数列表 List list = new ArrayList(); //同;但是其赋值依赖c,定义声明分开 char

    52320

    排序算法-下(Java语言实现)

    这样就保证了值相同元素,合并前后先后顺序不变。所以,归并排序是一稳定排序算法。 第二,归并排序时间复杂度是多少? 归并排序涉及递归时间复杂度分析稍微有点复杂。...第三,归并排序空间复杂度是多少? 归并排序时间复杂度任何情况下都是 O(nlogn),看起来非常优秀。(待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是 O(n2)。)...对于递归代码时间复杂度,我前面总结公式,这里也还是适用。如果每次分区操作,都能正好把数组分成大小接近相等小区间,那快排时间复杂度递推求解公式跟归并是相同。...实际上,递归时间复杂度求解方法除了递推公式之外,还有递归树,树那一节我再讲,这里暂时不说。...你可能会说,我有很笨办法,每次取数组最小值,将其移动到数组最前面,然后剩下数组中继续找最小值,以此类推,执行 K 次,找到数据不就是第 K 大元素了吗?

    43410

    算法时间复杂度和空间复杂度计算

    1、算法时间复杂度 1.1算法时间复杂度定义: 进行算法分析时,语句总执行次数T(n)是关于问题规模n函数,进而分析T(n)随n变化情况并确定T(n)数量级。...1.2.推导大O阶方法 分析一算法时间复杂度步骤: 用常数1取代运行时间所有加法常数。 修改后运行次数函数,只保留最高阶项。 如果最高阶项存在且不是1,则去除与这个项相乘常数。...1.3 函数调用时间复杂度分析 int i, j; for(i=0; i < n; i++) { function(i); } void function(int count) { printf...平均运行时间是期望运行时间。 最坏运行时间是一种保证。应用,这是一种最重要需求,通常除非特别指定,我们提到运行时间都是最坏情况运行时间2....: return fun(++n) 递归实现,调用fun函数每次都创建1变量k。

    1.7K20
    领券