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

求解递归时间函数T(n) = T(n-127)+127/logn

递归时间函数T(n) = T(n-127) + 127/logn 是一个递归式,其中n是输入的规模。

这个递归式描述了一个递归算法的时间复杂度。为了求解这个递归时间函数,我们可以使用递归树或主定理来进行分析。

首先,我们可以观察到递归式中的递归部分是 T(n-127),表示规模为n-127的子问题。然后,我们将递归式展开,得到以下形式:

T(n) = T(n-127) + 127/logn = T(n-127-127) + 127/log(n-127) + 127/logn = T(n-127-127-127) + 127/log(n-127-127) + 127/log(n-127) + 127/logn = ... = T(n-k127) + Σ(127/log(n-i127)),其中i从0到k-1,k为n/127的整数部分

可以观察到,递归式的规模每次减少127,直到规模小于等于0为止。因此,递归树的高度为n/127,每层的代价为127/log(n-i*127)。

接下来,我们需要计算递归树的总代价。根据递归树的结构,每层的代价是不同的,因此我们需要对每层的代价进行求和。由于递归树的高度为n/127,我们可以得到以下求和公式:

总代价 = Σ(每层代价) = Σ(127/log(n-i*127)),其中i从0到n/127-1

然而,这个求和公式并没有一个简单的解析解。因此,我们可以使用近似方法来估计总代价。

首先,我们可以观察到每层的代价是递减的,因为当i增加时,log(n-i127)也会增加。因此,我们可以将每层的代价近似为最大值,即127/log(n-i127) ≈ 127/log(n-(n/127-1)*127)。

然后,我们可以将总代价近似为每层代价的平均值乘以递归树的高度,即:

总代价 ≈ (1/(n/127)) * Σ(127/log(n-(n/127-1)*127)),其中i从0到n/127-1

化简上述公式,我们可以得到:

总代价 ≈ 127 * Σ(1/log(n-(n/127-1)*127)),其中i从0到n/127-1

这个近似公式可以用来估计递归时间函数的总代价。

至于腾讯云相关产品和产品介绍链接地址,由于要求不能提及具体的云计算品牌商,我无法给出具体的推荐。但是,腾讯云作为一家知名的云计算服务提供商,提供了丰富的云计算产品和解决方案,可以根据具体需求选择适合的产品和服务。

希望以上回答能够满足您的要求。如果还有其他问题,请随时提问。

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

相关·内容

递归算法的时间复杂度分析

转自地址 http://blog.csdn.net/metasearch/article/details/4428865 在算法分析中,当一个算法中包含递归调用时,其时间复杂度的分析会转化为一个递归方程求解...这种递归方程是分治法的时间复杂性所满足的递归关系,即一个规模为n的问题被分成规模均为n/b的a个子问题,递归求解这a个子 问题,然后通过对这a个子间题的解的综合,得到原问题的解。...一、代入法 大整数乘法计算时间递归方程为:T(n) = 4T(n/2) + O(n),其中T(1) = O(1),我们猜测一个解T(n) = O(n2 ),根据符号O的定义,对n>n0,有...在第一类情况下,函数nlogb a 较大,则T(n)=O(nlogb a );在第三类情况下,函数f(n)较大,则T(n)=O(f (n));在第二类情况下,两个函数一样大,则T(n)=O(nlogb...a *logn),即以n的对数作为因子乘上f(n)与T(n)的同阶。

1.9K50

数据结构与算法 - 时间复杂度

如果把问题看作函数,则算法就能把输入转化成输出。 在数据结构中,算法是对特定问题求解步骤的一种描述,是指令的有限序列。...通常情况下,时间复杂度的表示以O(f(n))形式体现,如O(1)、O(n)、O(n²)、O(logn)、O(2^n )等。...语句总执行次数为T(n)=1+1=2 因此,算法的时间复杂度为常数阶O(1)。算法的执行时间与问题规模n无关。 【例2】递归算法实现求n!,试分析时间复杂度。...} } 分析:语句(1)的时间复杂度为O(1),递归调用fact(n-1)的时间T(n-1),因此可得 当n≤1时,T(n) = O(1), 当n>1时:T(n) = T(n-1) + O(1),T...由此可推出 T(n)=(n-1)0(1)+T(1)=O(n) 因此递归n!算法的时间复杂度为O(n)。

68430
  • 快速排序

    5.1 时间复杂度最好情况划分后,左子序列和右子序列的长度相同,时间复杂度为 O(logn),递推公式如下:T(1) = C; n = 1 时,只需要常量级的执行T(n) = 2 * T(n/2) +...n; n>1递归公式的求解比较复杂,我们也可以根据递归树来求解。...平均时间复杂度假设每次分区操作都将区间分成 9:1 的两个小区间,时间复杂度为 O(nlogn),递归公式变成如下:T(1) = C; n = 1 时,只需要常量级的执行T(n) = T(n/10)...5.2 空间复杂度主要是递归造成的栈空间的使用。最好情况递归树深度为 logn,每次递归中只使用了常数的空间,空间复杂为 O(logn)。...最坏情况需要进行 n-1 次递归,每次递归中只使用了常数的空间,空间复杂度为 O(n)平均空间复杂度O(logn)

    15420

    算法设计关于递归方程T(n)=aT(nb)+f(n)之通用解法

    算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法 在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n),本文针对形如T(n)=aT(n/b)+f(n)的递归方程进行讨论,以期望找出通用的递归方程的求解方式...设a≥1,b>1为常数,f(n)为函数T(n)=aT(n/b)+f(n)为非负数,令x=logba: 1. f(n)=o(nx-e),e>0,那么T(n)=O(nx)。...2. f(n)=O(nx),那么T(n)=O(nx logn)。...同样,在f(n)不是多项式的时候也可以通过的这种方式得到方程的解。 二、f(n)是一般函数 当f(n)不是n的多项式的时候,计算就会变得比较复杂,有时可能会也找不到最终的解。...综上所述,可以得出以下结论:在针对形如T(n)=aT(n/b)+f(n)的递归方程求解方法里,使用递归树是一种比较可行的通用办法。

    1.6K70

    剖析递归行为和递归行为时间复杂度的估算

    剖析递归行为和递归行为时间复杂度的估算 master公式:也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。 应用Master定理可以很简便的求解递归方程。...master公式的使用 递归行为形如: T(N) = a*T(N/b) + O(N^d) 均可用下面推到出时间复杂度 (1) log(b,a) > d -> 复杂度为O(N^log(b,a)) (2)...log(b,a) = d -> 复杂度为O(N^d * logN) (3) log(b,a) 复杂度为O(N^d) T(N):       递归时间复杂度 N:            ...):    所有子过程的时间复杂度 O(N^d) :    除去子过程之外剩下过程的时间复杂度 注意: 1.使用master公式推到时间复杂度必须保证每次划分的子工程的规模是一样的 如果形如:...T(N) = T(N/3) + T(N/2) 这样一次分3份 一次份2份,是不可以用master推导的

    50230

    递归算法时间复杂度分析

    递归算法时间复杂度分析 时间复杂度: 一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定Tn)的数量级。...在我们求解递归式时,因为最终是要求得一个时间上限,所以在求解时常常省略一些细节。...经验和一些定理告诉我们,这些细节不会影响算法时间复杂度的渐近界。   类似的,我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是,迭代法一般适用于一阶的递推方程。...这个递推式将规模为n的问题分解为a个子问题,每个子问题的规模为n/bn/b,a个子问题递归求解,每个花费时间T(n/b)T(n/b)。函数f(n)f(n)包含了问题分解和子问题解合并的代价。...logn就可以了。

    2.4K20

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

    三个求解分治法Θ或Ω的方法 1、代入法 即假设一个界,然后数学归纳法证明 这种方法需要经验的积累,可以通过转换为先前见过的类似递归式来求解。...图八 递归树式子需要解释的地方有 cn其实就是一个函数f(n),这个函数所代表的意思是分解和合并步骤所花费的时间,哈哈 其(f(n))复杂度为Θ(n),由此再去理解图七中的式子就好理解了 下面来用递归树的方法求分治算法的渐进界...: 下边这是ppt上的例子,怎么理解这个递归树例子呢,最顶层是cn,从它开始递归,首先你可以把n理解为2的某次幂,比如,n是2的4次幂,所以整个递归树就有(logn)也就是4层,每一层的代价刚好都是cn...,可求出其Tn),第5层也就是常量的,为Θ(n),也可以回去图八和图七解释,哈哈 ?...T(n) = aT(n/b) + f (n) ,函数f(n),这个函数所代表的意思是分解和合并步骤所花费的时间 下图就是主定理,记住就行,也可以自己去推导一蛤~ ?

    1K70

    线性时间选择(Top K)问题(Java)

    例如,找n个元素的最小元素和最大元素显然可以在O(n)时间完成。如果k=n-n/logn时也一样。 2、分治法求解 一般的选择问题, 特别是中位数的选择问题似乎比找最小元素要难。但事实上, 从渐近阶的意义上看,它们是一样的。...例如,若ε=9/10,算法递归调用所产生的子数组的长度至少缩短1/10。所以,在最坏情况下,算法所需的计算时间T(n)满足递归T(n)≤T(9n/10)+O(n) 。...这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20 =εn,0<ε<1。这是使T(n)=O(n)的关键之处。当然,除了5和75之外,还有其他选择。...分析:递归调用 1、求x的工作量与中位数集合的规模有关,其值=n/t有关,t为每组元素数,t越大,其规模越小 2、规约后子问题大小与分组元素数t有关,t越大,子问题规模大。

    76610

    数据结构:时间和空间复杂度

    :事后分析,事前分析 空间效率 时间复杂度 时间复杂度的定义:在计算机科学中, 算法的时间复杂度是一个函数 ,算法中的基本操作的执行次数,为算法的时间复杂度。...):是用于描述函数渐进行为的数学符号 1 、用常数 1 取代运行时间中的所有加法常数。...) 次, 时间复杂度为 O(logN)(可以通过折纸得出) 5.递归 long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-...1)*N; } 递归N时间复杂度: O(N )每次递归函数消耗累加起来 6.嵌套循环 #include using namsespace std; void...long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; } 递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间

    9110

    复杂度O

    1. big O的含义 在学术界,严格地讲,O(f(n))表示算法执行的上界。比如,归并排序算法的时间复杂度是O(nlogn)的,同时也是O(n^2) 在业界,我们就是用O来表示算法执行的最低上界。...O(logn) 二分查找法的时间复杂度是O(logn)的 不要看到for循环,就认为是一层O(n),下面是两个例子 例1: 不是O(n^2),而应该是O(nlog(n))。...再来看一下O(logn)的效率: log2*N / logN = (log2 + logN) / logN = 1 + log2/logN 如果数据规模增加两倍,当数据量很大的时候,后面的一项可以忽略不计...递归 6.1 递归中进行一次递归调用的复杂度分析: 时间复杂度:O(logn) 如果递归函数中,只进行一次递归调用,递归深度为depth;在每个递归函数中,时间复杂度为T;则总体的时间复杂度为O(T*...例题: 根据前面O(logn)的性质,可知上面的幂运算比O(n)快很多。 6.2 递归中进行多次调用,以两次调用为例: 上面函数和归并排序不同,归并排序每次递归数据量都有减少,也就是分治算法。

    41410

    分治法-大整数乘法

    2、cp函数:将一个n位的数,分成两个n/2的数并存储,记录它的长度和次幂。 3、mul函数,不断地分解,直到有一个乘数为1位数时停止分解,进行乘法并记录结果。...4、add函数,将分解得到的数,进行相加合并。 代码流程: 初始化:将a、b倒序存储在数组a.s[],b.s[]中。 分解:cp函数:将一个n位的数,分成两个n/2的数并存储,记录它的长度和次幂。...转换为4次乘法运算:ah*bh,ah*bl,al*bh,al*bl: 求解子问题: ah*bh,ah*bl,al*bh,al*bl 继续求解子问题: 上述4个乘法运算都有一个乘数为1位数,可以直接进行乘法运算...算法复杂度分析: 假设两个n位大整数相乘的时间复杂度为T(n),则: 当n>1时,可以递推求解如下: 递推最终的规模为1,令n=2^x,则x=logn,那么有: 大整数乘法的时间复杂度为O(n...空间复杂度: 程序中变量占用了一些辅助空间,都是常数阶,但合并时结点数组占用的辅助空间为O(n),递归调用所使用的栈空间时O(logn)。所以,空间复杂度为O(n)。

    60640

    javascript:算法笔记

    return; } } } 向堆中添加新元素 //向堆H中添加元素x //时间复杂度O(logN) function insert...时间复杂度分析:创建堆需要O(n)的代价,每次siftDown代价为O(logN),最多调整n-1个元素,所以总代价为 O(N) + (N-1)O(logN),最终时间复杂度为O(NLogN) ...//堆中的节点下移 //(约定有效元素从下标1开始) //i为要调整的元素索引 //n为待处理的有效元素下标范围上限值 //时间复杂度O(logN) function...,有些场景中,递归的效率反而更高,比如计算x的m次幂,常规算法,需要m次乘法运算,下面的算法,却将时间复杂度降到了O(logn) //计算x的m次幂(递归实现) //时间复杂度O(logn...= split(A, low, w); //分治思路,先分成二半 w = t[1]; //在前一半求解 quickSort(A,

    1.2K100

    数据结构算法的时间复杂度_数据结构中排序的时间复杂度

    数据结构之算法时间复杂度 原文链接 算法的时间复杂度定义为: 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。...其中f( n)是问题规横n的某个函数。 根据定义,求解算法的时间复杂度的具体步骤是: 找出算法中的基本语句   算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。...就得到了 T(n) = 3n^2 + 3n + 1) 第二步:“在修改后的运行次数函数中,只保留最高阶项”。...%d disk from %c to %c \n", n, a, c); //执行一次 hanoi(n-1, b, a, c); //递归n-1次 } } 对于递归函数的分析...,跟设计递归函数一样,要先考虑基情况(比如hanoi中n==1时候),这样把一个大问题划分为多个子问题的求解

    85810

    【算法分析】分治法详解+范例+习题解答

    有一个矩阵,从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,求解总共有多少种走法的函数f(x,y),可以理解x是方格的横坐标、y是纵坐标,x≥0,y≥0。...然后递归地对子数组进行排序,最后将所得到的个排好序的子数组合并成所要求的排好序的数组。以上排序算法的平均时间复杂度是多少?...Θ(√n*log√n) 3.4.2快速排序 low和high是索引 void QuickSort ( SqList &L, int low, int high ){ //在序列lowhigh 中递归地进行快速排序...Partition时间复杂度Θ(n) 3.4.2.1复杂度 平均时间复杂度Θ(n*logn) 最坏时间复杂度O(n2) 平均空间复杂度O(logn),logn次都需要一个空间存基准 3.5线性时间选择算法...3.6.1复杂度 平均时间复杂度情况下,是Θ(n) 最坏时间复杂度O(n2) 4.书后习题 2-4 大整数乘法的O(nm log(3/2)) 2-5 2-27 以中位数为基准的选择问题

    2.4K30

    冰与火之歌:「时间」与「空间」复杂度

    冰之哀伤:时间复杂度 大O符号表示法 大O表示法:算法的时间复杂度通常用大O符号表述,定义为 **T[n] = O(f(n)) **。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。...递归算法的时间复杂度 如果递归函数中,只进行一次递归调用,递归深度为depth; 在每个递归函数中,时间复杂度为T; 则总体的时间复杂度为O(T * depth)。...根据数学知识,需要log2n次才能递归到底。因此,二分查找法的时间复杂度为 O(logn)。 求和 ?...1//递归深度:logn 2//时间复杂度:O(logn) 3double pow( double x, int n){ 4 if (n == 0) return 1.0; 5 6 double t...= pow(x,n/2); 7 if (n %2) return x*t*t; 8 return t * t; 9} 递归深度为 logn,因为是求需要除以 2 多少次才能到底。

    70410

    【趣学算法】Day4 分治算法——二分搜索

    :         sort 排序函数时间复杂度为 O(nlogn),如果数列本身有序,那么这部分不用考虑。...如果用 T(n) 表示 n 个有序元素的二分查找算法的时间复杂度,那么         1)当 n = 1 时,需要进行一次比较,T(n) = O(1)。        ...当 n = 1 时,T(n) = O(1);当 n > 1 时,T(n) = T(n / 2) + O(1)。         3)当 n > 1 时,可以进行递归求解。        ...(1)                 =……                 = T(n / 2 的x次方) + xO(1) 递归最终的数据规模为1,也就是说,n / 2 的x次方 = 1。...由于 n = 2 的x次方,因此 x = logn。 二分查找算法的时间复杂度为O(logn) (2)空间复杂度:         辅助空间是一些变量,它们是常数阶的,因此空间复杂度为O(1)。

    22920

    算法概论

    算法是对特定问题求解步骤的一种描述,如果将问题看作函数,那么算法是把输入转化为输出 对特定问题求解步骤的一种描述,是为了解决一个或者一类问题给出的 一个确定的、有限长的操作序列。...n的增长,算法执行时间的增长率和问题规模的增长率相同则可记为: Tn) = O(f(n)) f(n) 为问题规模n的某个函数Tn)被称为算法的(渐进)时间复杂度(Time Complexity)...O表示法不需要给出运行时间的精确值; 选择f(n),通常选择比较简单的函数形式,并忽略低次项和系数 常用的有O(1)、O(logn)、O(n)、O(nlogn)、O(n*n)等等 多项式时间复杂度的关系为...: O(1) < O(logn) < O(n) < O(N logn) < O(n²) < O(n³) 指数时间算法的关系为: O(2(n方))< O(n!)...我们需要从时间复杂度和空间复杂度两个维度来考虑。 常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划,缓存算法等 降低空间复杂度的方法:就要围绕数据结构做文章了。

    55940
    领券