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

我如何找到这个递归的渐近紧界?T(n) = T(n-2) + (n/2)

递归的渐近紧界是指递归函数的时间复杂度的上界和下界。对于给定的递归函数T(n) = T(n-2) + (n/2),我们可以通过递归树或递推关系来找到其渐近紧界。

首先,我们可以通过递归树来观察递归函数的执行过程。假设初始值为T(0) = 0,我们可以得到以下递归树:

代码语言:txt
复制
T(n)
   |
   T(n-2)
   |
   T(n-4)
   |
   T(n-6)
   |
   ...
   |
   T(0)

从递归树中可以看出,每一层的递归调用都会减少n的值,直到n减少到0为止。因此,递归树的高度为n/2。而每一层的递归调用都需要O(1)的时间复杂度,所以总的时间复杂度为O(n/2) = O(n)。

另一种方法是通过递推关系来求解递归函数的渐近紧界。我们可以将递归函数展开得到:

T(n) = T(n-2) + (n/2) = T(n-4) + ((n-2)/2) + (n/2) = T(n-6) + ((n-4)/2) + ((n-2)/2) + (n/2) = ... = T(0) + (2/2) + (4/2) + (6/2) + ... + (n/2)

可以观察到,每一项的分子都是一个等差数列,而分母都是2。我们可以将分子进行求和得到:

2 + 4 + 6 + ... + n = 2 * (1 + 2 + 3 + ... + (n/2))

等差数列求和公式为:S = (n/2) * (a + l),其中n为项数,a为首项,l为末项。将公式应用到上述等差数列中,可以得到:

S = (n/2) * (2 + (n/2)) = (n/2) * (n/2 + 2) = (n/2) * (n/2) + (n/2) * 2 = (n^2)/4 + n

因此,递归函数的时间复杂度为O((n^2)/4 + n) = O(n^2)。

综上所述,递归函数T(n) = T(n-2) + (n/2)的渐近紧界为O(n^2)。

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

相关·内容

算法导论第四章分治策略剖根问底(二)

递归方法非常直观,总代价就是把所有层次代价相加起来得到。但是分析这个总代价规模却不是件很容易事情,有时需要用到很多数学知识。...就像上面所说,该方法不能用于所有的形如上式递归式,f(n)和nlogba关系必须是多项式意义上小于大于,即渐近关系(渐近小于、渐近大于),什么是渐近,就是两者相差一个因子nε。...递归树法: 1)、对递归T(n) = 3T(n/2) +,利用递归树确定一个好渐近上界,用代入法进行验证。 ?...2)、对递归T(n) = T(n/2) + n2,利用递归树确定一个好渐近上界,用代入法进行验证。 ? 主方法: 1)、对于下列递归式,使用主方法求出渐近。   ...a、T(n) = 2T(n/4) + 1   b、T(n) = 2T(n/4) + n1/2   c、T(n) = 2T(n/4) + n   d、T(n) = 2T(n/4) + n2 ?

1.6K60

可能是最可爱一文读懂系列:皮卡丘の复杂度分析指南

Big Theta(Θ):算法行为严格约束,此符号定义函数上界和下界。这称为,因为我们将运行时间限制在上下两个常量因子内。就像这样: ? C1和C2是常量。...f(N)是运行时间函数,g(N)是 每个算法可能有不同最佳和最差情况。当两者相同时,我们倾向于使用Θ表示法。...否则,最佳和最差情况需要被分别表示: (a)对于很大N值,最差情况 f(N)受函数g(N) = N限制。因此,复杂度将表示为Θ(N)。...这意味着最坏情况下皮卡丘搜索时间是最少要C1⋅N,最多要C2N。 (b)类似地,其最佳情况复杂度是Θ(1)。 ? 空间复杂度 我们之前一直在讨论时间复杂度。...我们甚至看到了一些有效和正确分析这种复杂性优秀技术,以便及时做出明智决策。然而,问题出现了, 鉴于我所知道两种算法时间和空间复杂性,如何选择最终使用哪种算法?有黄金法则吗?

91150
  • 算法基础+分治策略(算法复习第1弹)

    f(n)=Θ(g(n)) 图一 称g(n)是f(n一个渐进,也就是f(n)得在c1g(n)和c2g(n)之间,不得越界 举个例子证明(考点): ? 证明这个式子 ?...图八 递归树式子需要解释地方有 cn其实就是一个函数f(n),这个函数所代表意思是分解和合并步骤所花费时间,哈哈 其(f(n))复杂度为Θ(n),由此再去理解图七中式子就好理解了 下面来用递归方法求分治算法渐进...: 下边这是ppt上例子,怎么理解这个递归树例子呢,最顶层是cn,从它开始递归,首先你可以把n理解为2某次幂,比如,n24次幂,所以整个递归树就有(logn)也就是4层,每一层代价刚好都是cn...,可求出其Tn),第5层也就是常量,为Θ(n),也可以回去图八和图七解释,哈哈 ?...T(n) = aT(n/b) + f (n) ,函数f(n),这个函数所代表意思是分解和合并步骤所花费时间 下图就是主定理,记住就行,也可以自己去推导一蛤~ ?

    1K70

    算法之美——算法复杂性

    多年来,有一个梦想,希望每一位提到算法的人,不再立即皱眉头,脑海闪现枯燥公式、冗长代码;希望每一位阅读和使用算法的人,体会到算法之美,像躺在法国普罗旺斯小镇长椅上,呷一口红酒,闭上眼睛,体会舌尖上美味...算法1-2的确算得挺快,但如何知道算法好不好呢? “好”算法标准如下。...图1-1 渐近时间复杂度上界 还有渐近下界符号Ω(T(n) ? Cf (n)),如图1-2所示。 ? 图1-2 渐近时间复杂度下界 从图1-2可以看出,当n ? n0时,T(n) ?...Cf (n),当n足够大时,T(n)和f (n)近似相等,因此,我们用Ω(f (n))来表示时间复杂度渐近下界。 渐近精确符号Θ(C1f (n) ? T(n) ?...这种两边逼近方式,更加精确近似,因此,用Θ (f (n))来表示时间复杂度渐近精确。 ? 图1-3 渐进时间复杂度精确 我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。

    1.1K10

    数据结构 第2讲 算法复杂性

    多年来,有一个梦想,希望每一位提到算法的人,不再立即皱眉头,脑海闪现枯燥公式、冗长代码;希望每一位阅读和使用算法的人,体会到算法之美,像躺在法国普罗旺斯小镇长椅上,呷一口红酒,闭上眼睛,体会舌尖上美味...算法1-2的确算得挺快,但如何知道算法好不好呢? “好”算法标准如下。...图1-1 渐近时间复杂度上界 还有渐近下界符号Ω(T(n) ? Cf (n)),如图1-2所示。 ? 图1-2 渐近时间复杂度下界 从图1-2可以看出,当n ? n0时,T(n) ?...Cf (n),当n足够大时,T(n)和f (n)近似相等,因此,我们用Ω(f (n))来表示时间复杂度渐近下界。 渐近精确符号Θ(C1f (n) ? T(n) ?...这种两边逼近方式,更加精确近似,因此,用Θ (f (n))来表示时间复杂度渐近精确。 ? 图1-3 渐进时间复杂度精确 我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。

    88120

    《算法设计与分析》期末不挂科原因_算法设计与分析重点

    渐近上界记号 渐近下界记号 非上界记号 非下界记号 渐近记号 意义 算法分析中常见复杂性函数 算法分析方法 算法分析基本法则 递归 基本概念 递归优缺点 递归树方法 主方法 主定理...算法时间复杂性 算法渐近复杂性 渐近分析记号 渐近上界记号 渐近下界记号 非上界记号 非下界记号 渐近记号 意义 算法分析中常见复杂性函数 算法分析方法...每个子问题n/b未必为整数,但用T(n/b)代替T(⌈n∕b⌉)和T(⌊n∕b⌋ )并不影响递归方程渐近行为,因此我们在表达这种形式分治算法时将略去向下取整函数和向上取整函数。...这个过程一直持续到找到所需解或活结点表为空时为止。...自然地导出递归斐波那契过程 F(n) F(n) 1 if n2 2 then return 1 3 return F(n-1)+F(n-2) 分治法计算时间递归方程: 活动选择问题递归方程

    1.1K20

    《算法设计与分析》学习笔记

    渐近记号 ①渐近上界记号O 渐近地给出一个函数在常量因子内上界: O(g(n)) = { f(n) : 存在正常量c和n0,使得对所有nn0,有0 ≤ f(n) ≤ cg(n)} O可用于标识最坏情况运行时间...≥ n0 } Ω可用于标识最佳情况运行时间 ③渐近记号 Θ 渐近地给出了一个函数上界和下界:Q(g(n)) = { f(n) : 存在正常量c1, c2n0,使得对所有nn0,有0 ≤...④非渐近确上界记号o o(g(n)) = { f(n) | 对于任何正常量c > 0,存在常量n0  > 0使得对所有n ³ n0,有0 ≤ f(n) < cg(n) } ⑤非渐近确下界记号ω ω(...递归树 图片 图片 代入法 T(n) = T(n/2) + n² 假设T(n)∈O(n²),证明T(n)≤cn²: 图片 主方法 主方法可解如下形式递归T(n) = aT(n/b) + f(n...换句话说,对于一个给定NP问题,如果我们有一个解,我们可以在多项式时间内验证这个正确性。然而,我们并不能在多项式时间内找到一个解。

    27620

    解析时间复杂度和空间复杂度

    1.算法效率 1.1 如何衡量一个算法好坏 算法好坏有很多点,效率高,运行时间短就是其中一点。...long long Fib(int n) { if(n<3) return 1; return Fib(n-1)+Fib(n-2); } 这是一个求斐波那契数递归函数,看起来很简洁,但效率其实非常低...在一个长度为N数组中搜索一个数据x 最好情况:一次找到 最坏情况:N找到 平均情况:N/2找到 在实际中一般情况关注是算法最坏情况,所以数组中搜索数据时间复杂度为O(N) 2.3 常见时间复杂度计算练习...flag == 0) break; } } 时间复杂度:O(N^2),计算时间复杂度要从算法原理计算,冒泡排序本质是什么 ​冒泡排序:两两比较,第一趟会比较n-1次,第二趟会比较n-2次,...空间复杂度不是程序占用了多少Bytes字节,因为计算这个没什么意义,所以空间复杂度算变量个数。空间复杂度计算规则和时间复杂度类型,也使用大O渐近表示法。

    8110

    文心一言 VS 讯飞星火 VS chatgpt (285)-- 算法导论21.2 4题

    图21-3所示操作序列是一个链表操作序列,我们需要找出这个操作序列运行时间渐近。这是一个关于数据结构问题,特别是链表和加权合并启发式策略。...在这个问题中,我们可以使用Go语言来实现一个链表,并使用加权合并启发式策略来优化链表合并操作。这样,我们就可以得到操作序列运行时间渐近。...360智脑: 很抱歉,由于我无法直接查看图21-3或任何其他图像,因此不能为您提供该图所示操作序列渐近。如果您能提供更多关于操作序列或相关算法详细信息,可能能够帮助您分析其时间复杂度。...智谱清言: 抱歉,由于您请求中没有提供图21-3详细信息,无法给出具体操作序列或其运行时间渐近。此外,没有具体操作序列,也无法为您提供使用Go语言编写代码。...如果您能提供更多关于图21-3详细信息,例如其中节点、边以及相关操作,将很乐意帮助您分析其运行时间并给出渐近

    9020

    算法复杂性分析

    在数学上,T’(N)是T(N)当N→∞时渐进表达式。例如:3N2+4NlogN+7与3N2, 3N2是3N2+4NlogN+7渐近表达式。...算法复杂性在渐近意义下记号有:O、Ω、Θ等,分别表达运行时间上界、运行时间下界、运行时间准确等 2.2.1 运行时间上界 设函数f(n)和g(n)是定义在非负整数集合上正函数,如果存在正整数...= O(nn) 对于n≥1,有n(n-1)(n-2) … 1≤nn,因此,可选c=1,n0=1。对于nn0,f(n)= n!≤nn,所以,f(n) = O(nn)。...2.2.3 运行时间准确 设有函数f(n)和g(n)是定义在非负整数集合上正函数,如果存在正整数n0和正常数c1和c2(c1 ≤c2),使得当nn0时,有c1 g(n)≤f(n)≤c2 g(n...最常见多项式时间算法渐近时间复杂度。 O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(n^3) 最常见指数时间算法渐近时间复杂度。 O(2^n)<O(n!)

    1.1K30

    为什么快速排序算法效率比较高?

    f(10)=9+8+7+......+1 ,可以转为一个等差数列: f(n)=(n-1)+(n-2)+(n-3)+......+1= (n-1)*n / 2 = 0.5n^2-0.5n 按照上篇文章中介绍复杂度渐近表示...下面我们来分析下快排Ο(nlog2n)时间复杂度如何得来,假设我们随机取基准数总是能把整个数组给平均切成2个子数组: 快排简化版代码如下: quick_sort(n){.../2,array.length) //递归快排后n/2个元素 } 在《算法导论》第三版101页,可见快速排序递推式为:T(n)=max(T(q) + T(n-q-1)) +O(n),q为切分长度...换一下加法项位置,T(n)=O(n)+2T(n/2),不正是上面的规律吗?第一次比较 9 次,因此 T(10)=9+2T(5),而 T(5)=5+2T(2.5)。...快速排序每次都会以2为低做裂变分解数组,所以最终推出来渐近复杂度:Ο(nlog2n) 下面我们以随机生成1万个数字,分别用冒泡排序和快速排序来测试: 根据时间复杂度推算: 冒泡排序需要比较次数:1万平方阶

    9.5K30

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

    2 == n) return 2; return fib(n-1)+fib(n-2); } 3.1时间复杂度分析 以递归实现斐波那契数,效率是非常低下,因为对子问题求解...因为n-(n-2)=2,所以是二阶,函数值f(n),f(n-1)和f(n-2)指数是1,且系数均是常数,所以是线性常系数,又因为常数项为0,即等号右边为0,所以是齐次。...知道时间度复杂常见有且依序复杂度递增: O(1), O(lgn),O(n√)O(\sqrt n),O(n),O(nlgn),O(n2)O(n^2 ),O(n3)O(n^3 ),O(2n)O...因为上面的递归实现,虽然每次递归都会有开辟两个分支,按理说递归调用了 多少次,就开辟了多大栈空间,按照这个逻辑,那么空间复杂度与时间复杂应该是一样, 都是O(2n)O(2^n)。...image.png 因而计算f(n)就简化为计算矩阵(n-2)次方,而计算矩阵(n-2)次方,我们又可以进行分解,即计算矩阵(n-2)/2次方平方,逐步分解下去,由于折半计算矩阵次方,因而时间复杂度为

    1.1K22

    文心一言 VS chatgpt (6)-- 算法导论2.3 3~4题

    现假设对于所有的 k<m,递归T(n)=nlgn 成立,即当 n 刚好是 2 幂时,T(n)=nlgn。 考虑当 n=2^m 时,如何证明 T(n)=nlgn。...为了排序 A[1..n],我们递归地排序A[1..n-1],然后把 A[n]插入已排序数组 A[1..n-1]。为插人排序这个递归版本最坏情况运行时间写一个递归式。...文心一言: 为了排序 A[1..n],我们递归地排序A[1..n-1],然后把 A[n]插入已排序数组 A[1..n-1]。为插人排序这个递归版本最坏情况运行时间写一个递归式。...因此,插入排序递推式为: T(n) = T(n-1) + (n-1) 展开递归式,可以得到: T(n) = T(n-2) + (n-2) + (n-1) = T(n-3) + (n-3) +...因此,插入排序递归版本最坏情况运行时间递归式为: T(n) = 1 + 2 + ... + (n-2) + (n-1) + n 可以用等差数列求和公式求出该递归解为: T(n) = Θ(n^2)

    15820

    青蛙跳台阶

    return fib(n-1)+fib(n-2); } 5.1 时间复杂度 以递归实现斐波那契数,效率是非常低下,因为对子问题求解 fib(n-1) 和 fib(n-2) 两者存在重叠部分,对重叠部分重复计算造成了浪费...所以,f(n)通解为: 由f(1)=1,f(2)=2可解得c1=(5+√5)/10, c2 ==(5-√5)/10,最终可得时间复杂度为: 知道时间度复杂常见有且依序复杂度递增:...因为上面的递归实现,虽然每次递归都会有开辟两个分支,按理说递归调用了 多少次,就开辟了多大栈空间,按照这个逻辑,那么空间复杂度与时间复杂应该是一样, 都是 O(2^n) 。...图中示例是单线程情况下递归函数执行流程,但是在多线程情况下,就不是这个样子,因为每个线程函数并发执行,拥有自己函数栈,所以空间复杂度要另当计算,这里就不做深究,有兴趣读者可自行研究。...因而计算 f(n) 就简化为计算矩阵 (n-2) 次方,而计算矩阵 (n-2) 次方,我们又可以进行分解,即计算矩阵 (n-2)/2 次方平方,逐步分解下去,由于折半计算矩阵次方,因而时间复杂度为

    95520

    算法导论第四章分治策略实例解析(一)

    三个量分别是:确定一个函数渐近上界Ο符号,渐近下届Ω符号,以及渐近Θ符号,这是在分析一个算法界限时常用分析方法,具体就详看书本了,对于我们更多关注上层算法表达来说,这些显得不是那么重要,...理解是Ο可以简单看成最坏运行时间,Ω是最好运行时间,Θ是平均运行时间。...二、第四章两大板块   第四章讲递归,也是数学东西太多了,准备这样来组织这章结构:先用一个例子(最大子数组和)来讲解用到递归一个经典方法——分治法,然后在引入如何递归式,即引入解递归三种方法...要求时间复杂度是O(n),我们暂且不管这个,由浅入深地分析一下这道题,时间复杂度从O(n^2)->O(nlgn)->O(n)。...动态规划严格遵循递推式,而区间法是寻找使区间变化标识,即和是否小于零,而这个标识正是动态规划采用

    1.2K100

    为什么你学不会递归?告别递归,谈谈一些经验

    递归三大要素 第一要素:明确你这个函数想要干什么 对于递归觉得很重要一个事就是,这个函数功能是什么,他要完成什么样一件事,而这个,是完全由你自己来定义。...少侠,请继续看,下面还会讲如何优化递归。当然,大佬请随意,可以直接拉动最下面留言给我一些建议,万分感谢!...第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没,剩下n-2个台阶跳法有f(n-2)种。 所以,小青蛙全部跳法就是这两种跳法之和了,即 f(n) = f(n-1) + f(n-2)。...就像上面,f(n-2)这个函数调用,有可能出现 f(0) 情况,导致死循环,所以我们把它补上。...通过一篇文章是不可能掌握递归,还得多练,相信,只要你认真看我这篇文章,多看几次,一定能找到一些思路!!

    50400
    领券