免费智能真题库 > 历年试卷 > 软件设计师 > 2025年下半年 软件设计师 上午试卷 综合知识
  第6题      
  知识点:   递归式
  关键词:   时间复杂度   算法        章/节:   计算机软件知识       

 
某算法的时间复杂度可用递归式= 表示,若用表示,则正确的是(64)。
 
 
  A. 
 
  B. 
 
  C. 
 
  D. 
 
 
 

  相关试题:计算机软件知识          更多>  
 
  第64题    2011年下半年  
   46%
  第62题    2012年下半年  
   33%
将数组{1,1,2,4,7,5}从小到大排序,若采用(62)排序算法,则元素之间需要进行的比较次数最少,共需要进行(63)次元素之间的比较。..
  第61题    2023年上半年  
   45%
设由三棵树构成的森林中,第一棵树、第二棵树和第三棵树的结点总数分别为n1、n2和n3。将该森林转换为一棵二叉树,那么该二叉树的..
   知识点讲解    
   · 递归式
 
       递归式
        从算法的结构上看,算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单,本小节主要讨论递归算法的时间复杂度分析方法。
        (1)展开法。将递归式中等式右边的项根据递归式进行替换,称为展开。展开后的项被再次展开,如此下去,直至得到一个求和表达式及其结果。
        (2)代换法。这一名称来源于当归纳假设用较小值时,用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤:猜测解的形式;用数学归纳法找出使解真正有效的常数。
        (3)递归树法。递归树法弥补了代换法猜测困难的缺点,它适于提供"好"的猜测,然后用代换法证明。在递归树中,每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时,递归树的方法尤其有用。
        (4)主方法。也称为主定理,给出求解以下形式的递归式的快速方法,即
        T(n)=aT(n/b)+f(n)
        式中,a≥1和b>1是常数;f(n)是一个渐进的正函数。
   题号导航      2025年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第6题    在手机中做本题