首页
学习
活动
专区
工具
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)。

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

相关·内容

数据结构·复杂度

1 时间复杂度 时间复杂度定义上可以认为使劲按复杂度是一函数,定量描述了算法所需要时间,但是理论上来说,运行时间是要上机测试才能测试出来,实际测试就会花很多时间,所以有了时间复杂度这个分析方式分析算法执行基本操作次数...2修改后运行次数函数,只保留最高阶项。 3、如果最高阶项存在且不是1,则去除与这个项目相乘常数。得到结果就是大O阶。...1,每趟下来,就会确定一数据位置,所以两两比较次数每次都会减去1,那么if这个语句执行次数就是N - 1 N - 2……1,利用高中等差数列知识,可以得到时间复杂度函数是F(N) = (...Fac(N - 1) * N; } 递归函数里面加了一for循环,时间复杂度是多少呢?...那么递归计算斐波那契数列空间复杂度是多少呢?

6410

青蛙跳台阶

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

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

    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

    1.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乘以每个栈帧大小,即

    20110

    一文学会排列组合

    时间复杂度是多少呢,从以上步骤其实可以看到是第四步做快排时时间复杂度,即 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)操作。

    47211

    【初阶数据结构】——时间复杂度和空间复杂度详解(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) 所以,对于递归函数时间复杂度计算: 我们要算就是每次递归调用执行次数累加...这是我们计算时间复杂度是分析图,它递归调用了这么多次,但是,这么多分支,它们进行递归,开辟函数栈帧,是同时进行吗? 不是的。 它们是一分支,一分支按照先后顺序进行

    36610

    【数据结构】初识数据结构与复杂度总结

    3.1时间复杂度 时间复杂度定义:计算机科学,算法时间复杂度是一函数(注:这里函数是数学上函数,不是c语言函数!!!),它定量描述了该算法运行时间。...:任意输入规模最小运行次数(下界) 例如:长度为N数组搜索一数据x 最好情况:1次找到 最坏情况:N次找到 平均情况:N/2次找到 实际中一般情况关注是算法最坏运行情况,所以数组搜索数据时间复杂度为...O(N^2) 我们继续看一 这个是不是也是有点眼熟,对我之前总结猜数字游戏里二分查找,那它时间复杂度是多少那,我们先来想一想这个函数怎么实现,是每次查找缩小一半范围,相当于除2,查找一次除一次...O表示就是O(N) 再看一递归 这个空间复杂度是多少 它运行时创立了N函数栈帧,所以它结果为O(N) 我们来看一复杂点 这个时间复杂度我们知道了是O(2^N)空间复杂度那 这个我们要好好想想,...递归函数创建函数栈帧特点,第一列函数栈帧创建完,调用完再销毁,后几列函数递归再用第一列曾经函数栈帧所用空间,不会额外再开辟新函数栈帧,简单来说就是第一列函数递归深度就是它空间复杂度,后面的函数递归

    7010

    数据结构与算法:复杂度

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

    14210

    【数据结构与算法】递归

    (有规律每次调用函数处理数据会较上次缩减(子集),而且最后会缩减至无需继续递归 内层函数调用(子集处理)完成,外层函数才能算调用完成 原理 假设链表中有 3 节点,value 分别为 1,2...反向打印字符串 用递归反向打印字符串,n 为字符整个字符串 str 索引位置 递:n 从 0 开始,每次 n + 1,一直递到 n == str.length() - 1 归:从 n == str.length...斐波那契数列-Leetcode 70 之前例子是每个递归函数只包含一自身调用,这称之为 single recursion 如果每个递归函数例包含多个自身调用,称之为 multi recursion...,用不着我 b 了,我内存就可以释放 如果调用 a 时 不是尾调用,例如 return b() + 1,那么 a 就不能提前结束,因为它还得利用 b 结果做加法 尾递归递归是尾调用一种特例,也就是最后一步执行是同一函数...3) + c + c + c … T(n) = T(n-(n-1)) + (n-1)c 其中 T(n-(n-1)) 即 T(1) 带入求得 T(n) = c + (n-1)c = nc 时间复杂度

    14710

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

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

    91700

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

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

    10810

    一文学会递归解题

    什么是递归 简单地说,就是如果在函数存在着调用函数本身情况,这种现象就叫递归。...以阶乘函数为例,如下, 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),很明显指数级别的时间复杂度是不能接受,汉诺塔非递归解法比较复杂,大家可以去网上搜一下 进阶题 现实中大厂很多递归题都不会用上面这些相对比较容易理解

    46320

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

    什么是递归 简单地说,就是如果在函数存在着调用函数本身情况,这种现象就叫递归。...以阶乘函数为例,如下, 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),很明显指数级别的时间复杂度是不能接受,汉诺塔非递归解法比较复杂,大家可以去网上搜一下 进阶题 现实中大厂很多递归题都不会用上面这些相对比较容易理解

    62310

    【数据结构与算法基础】——算法复杂度

    ,主要衡量算法运行效率,用来估算算法不同规模下运行时间 时间复杂度用大O渐进表示法来表示 2.1时间复杂度计算 算法时间复杂度是一函数式T(N),它定量描述了该算法运行时间...通常将这些操作数量与输入规模相关联。 循环结构: 算法包含循环结构,需要考虑循环迭代次数以及每次迭代基本操作数量。...递归调用: 对于递归算法,需要考虑递归深度以及每次递归调用时间复杂度。通常使用递归方程(递归关系式)来表示递归算法时间复杂度。...Fac函数时间复杂度为O(1) 而一共有n次递归,所以阶乘递归时间复杂度为O(N) 三、空间复杂度 空间复杂度也是一数学表达式,是对一算法在运行过程因为算法需要额外临时开辟空间...递归调用了N次,额外开辟了N函数栈帧,每个栈帧使用了常数个空间 因此时间复杂度为:O(N) 感谢各位大佬支持并指出问题, 如果本篇内容对你有帮助,可以一键三连支持以下,感谢支持!!

    8110

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

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

    86710

    【基础算法】递归算法

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

    35810

    c语言函数递归迭代详解(含青蛙跳台阶问题详解)

    前言 1.递归是什么? 递归是学习C语言函数绕不开话题,那什么是递归呢? 递归其实是一种解决问题方法,C语言中,递归就是函数自己调用自己。...这里有一极其简单递归代码: #include int main() { printf("1\n"); main();//main函数调用main函数 return 0;...递归限制条件 递归书写时候,有2必要条件: 递归存在限制条件,当满足这个限制条件时候,递归便不再继续 每次递归调用之后越来越接近这个限制条件。 在下面的例子,我们逐步体会这2限制条件。...("%d ", ADD(1, 2)); return 0; } 这是一简单地加法函数mian函数,printf对ADD返回值进行输出。...递归迭代 递归是一种很好编程技巧,但是和很多技巧一样,也是可能被误用,就像举例1一样,看到推导公式,很容易就被写成递归形式: Fact函数是可以产生正确结果,但是递归函数调用过程涉及一些运行时开销

    5810

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

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

    15310

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

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

    1.3K20
    领券