首页 > 其他分享 >求解递归时间复杂度

求解递归时间复杂度

时间:2023-09-14 09:22:08浏览次数:38  
标签:frac log 递归 求解 复杂度 16 sqrt times

迭代法

每一次对过程的重复称为一次迭代,而每一次迭代得到的结果会作为下一次迭代的初始值。重复执行一系列运算步骤,从前面的量依次求出后面的量的过程。

例1

problem:

\(T(n)=2 \times T(\frac{n}{4})+ \sqrt n,T(1)=1\)

solution:

\[T(n)=2 \times T(\frac{n}{4})+ \sqrt n \]

\[T(n)=2 \times (2 \times T(\frac{n}{16})+\sqrt \frac{n}{4})+ \sqrt n \]

\[T(n)=4 \times T(\frac{n}{16})+2 \times \frac{\sqrt n}{2}+ \sqrt n \]

\[T(n)=4 \times T(\frac{n}{16})+2 \sqrt n \]

\[\ldots \]

\[T(n)=2^k \times T(\frac{n}{2^{2k}})+k \sqrt n \]

令 \(2^{2k}=n\),即 \(2^k=\sqrt n\),\(k=\log_2^{\sqrt n}=\log_2^{n^{\frac{1}{2}}}=\frac{1}{2} \log_2^n\)

\[T(n)=\sqrt n \times T(1)+\frac{1}{2} \log_2^{n} \sqrt n \]

\[T(n)=\sqrt n +\frac{1}{2} \sqrt n \log_2^n \]

所以时间复杂度为 \(O(\sqrt n \log n)\)

标签:frac,log,递归,求解,复杂度,16,sqrt,times
From: https://www.cnblogs.com/reclusive2007/p/17701395.html

相关文章

  • 【智能优化算法】基于大逃杀优化算法BRO求解单目标优化问题附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 递归函数和其他拓展
    递归函数和其他拓展课前练习请实现一个装饰器,把'函数的返回值'+100然后'返回'defount(fun):defwerrod(*ardes,**warrrts):res=fun(*ardes,**warrrts)returnres+100returnwerrod@ountdeffuns(intes):returnint(intes)res=funs(100)......
  • 递归时间复杂度
    时间复杂度递归求斐波那契数列时间复杂度:O(2^n)递归树分析节点单一子问题代价:函数执行过程中,除去递归调用以外的代价比如:intfib(intn){ if(n==1||n==2){//前2项直接返回 return1; } returnfib(n-1)+fib(n-2);//第3项=前两项之和}1n=1或n=1时,return1时间......
  • 『具体数学』第1章 递归问题
      一切的开始。典例选讲hanoi塔  问题不加赘述。  想要解决问题,书中便借此问题引出一些解决问题的通法:先研究小的情形命名并求解  经过这两步与一些基础的构造,不难把hanoi塔问题变为一组递推式:\[\begin{array}{ll}&T_0=0;\\&T_n\leq2T_{n-1}+1,n>0.\end......
  • P3201 [HNOI2009] 梦幻布丁 启发式合并,时间复杂度
    [HNOI2009]梦幻布丁一种很暴力,很容易想到,但时间复杂度不对的做法:既然每一次修改是以颜色作为单位的,那就用set或者链表(vector)维护每一个颜色出现的位置。将颜色\(x\)改为\(y\)的时候,遍历\(list_x\)的每一个点,判断其左右是否为\(y\),更新ans(不同颜色块数量)时间复杂度最大为......
  • 例2.6 设计一个高效的算法,从顺序表L中删除所有值为x的元素,要求时间复杂度为0(n)空间复杂
    1.题目例2.6设计一个高效的算法,从顺序表L中删除所有值为x的元素,要求时间复杂度为0(n)空间复杂度为0(1)。2.算法思想3.代码voidDeleteX(SeqListLA,SeqList*LC,intx){inti=0,j=0;while(i<=LA.last){if(LA.element[i]==x)i++;else......
  • 空间复杂度
        ......
  • #yyds干货盘点#时间复杂度简述
    时间复杂度(1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执......
  • C语言函数递归 --- 复习题(1)
    一.单选题:1.下列选项关于递归说法错误的是()A.存在限制条件,当满足限制条件时,递归停止B.每次递归调用后越来越接近递归的条件C.递归可以无限制递归下去D.递归层次太深容易出现栈溢出答案:C,这题错误的选项显而易见是C,我们之前将递归的时候就说过递归的两个要求,第一个是需要有限制条......
  • 常见的算法时间复杂度
    1.常见的排序算法的平均时间复杂度、最好情况的时间复杂度、最坏情况的时间复杂度、稳定性、是否基于比较的表格 这里,n是要排序的元素数量,k是元素的取值范围。对于基于比较的排序算法,k没有意义,因为这些算法不关心元素的具体值,只关心元素之间的相对顺序。对于非基于比较的排序算......