免费智能真题库 > 历年试卷 > 软件设计师 > 2019年上半年 软件设计师 上午试卷 综合知识
  第64题      
  知识点:   动态规划法   算法分析基础
  章/节:   计算机软件知识       

 
已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A1A2......An相乘的计算顺序具有最优子结构,即A1A2......An的最优计算顺序包含其子问题A1A2......Ak和Ak+1Ak+2……An(1≤k<n)的最优计算顺序。
可以列出其递归式为:

其中,Ai的维度为pi-1*pi,m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数。
先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为(62)。算法的时间复杂度为(63),空间复杂度为(64)。
给定一个实例,(p0p1……p5)=(20,15,4,10,20,25),最优计算顺序为(65)。
 
 
  A.  O(n2)
 
  B.  O(n2lgn)
 
  C.  O(n3)
 
  D.  O(2n)
 
 
 

 
  第62题    2013年上半年  
   44%
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个元素ai和aj,使得ai+aj=x。为了求解该问题,首先用归并..
  第33题    2017年上半年  
   44%
模块A、B和C有相同的程序块,块内的语句之间没有任何联系,现把该程序块取出来,形成新的模块D,则模块D的内聚类型为(33)内聚。以..
  第64题    2011年下半年  
   46%
   知识点讲解    
   · 动态规划法    · 算法分析基础
 
       动态规划法
               动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。
               动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解,每个解都对应于一个值,希望找到具有最优值(最大值或最小值)的那个解。当然,最优解可能会有多个,动态规划算法能找出其中的一个最优解。设计一个动态规划算法,通常可按照以下几个步骤进行。
               (1)找出最优解的性质,并刻画其结构特征。
               (2)递归地定义最优解的值。
               (3)以自底向上的方式计算出最优值。
               (4)根据计算最优值时得到的信息,构造一个最优解。
               对一个给定的问题,若其具有以下两个性质,则可以考虑用动态规划法来求解。
               (1)最优子结构。如果一个问题的最优解中包含其子问题的最优解,就说该问题具有最优子结构。当一个问题具有最优子结构时,表示动态规划法可能会适用,但是此时贪心策略可能也是适用的。
               (2)重叠子问题。它指用来解原问题的递归算法可反复地解同样的子问题,而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时,就说明该问题包含重叠子问题。此时若用分治法递归求解,则每次遇到子问题都会视为新问题,会极大地降低算法的效率,而动态规划法总是充分利用重叠子问题,对每个子问题仅计算一次,把解保存在一个在需要时就可以查看的表中,而每次查表的时间为常数。
 
       算法分析基础
               时间复杂性
               算法的时间复杂度分析主要是分析算法的运行时间,即算法所执行的基本操作数。即使对相同的输入规模,数据分布不相同也决定了算法执行不同的路径,因此所需要的执行时间也不相同。根据不同的输入,将算法的时间复杂度分为3种情况。
               (1)最佳情况。使算法执行时间最少的输入。一般情况下,不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(nlgn),那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。
               (2)最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析,因为最坏情况是在任何输入下运行时间的一个上限,它提供了一个保障,情况不会比这更糟糕。另外,对于某些算法来说,最坏情况还是相当频繁的。而且大致上看,平均情况通常与最坏情况的时间复杂度一样。
               (3)平均情况。算法的平均运行时间。一般来说,这种情况很难分析。举个简单的例子,现要排序10个不同的整数,输入就有10!种不同的情况,平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。
               ①将所有的输入按其执行时间分类。
               ②确定每类输入发生的概率。
               ③确定每类输入的执行时间。
               下式给出了一般算法在平均情况下的复杂度分析,即
               
               式中,pi为第i类输入发生的概率;ti为第i类输入的执行时间,输入分为m类。
               渐进符号
               渐进符号有以下几种。
               (1)Ο记号。给出一个函数的渐进上界。
               (2)Ω记号。给出一个函数的渐进下界。
               (3)Θ记号。给出一个函数的渐进上界和下界,即渐进确界。
               递归式
               从算法的结构上看,算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单,本小节主要讨论递归算法的时间复杂度分析方法。
               (1)展开法。将递归式中等式右边的项根据递归式进行替换,称为展开。展开后的项被再次展开,如此下去,直至得到一个求和表达式及其结果。
               (2)代换法。这一名称来源于当归纳假设用较小值时,用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤:猜测解的形式;用数学归纳法找出使解真正有效的常数。
               (3)递归树法。递归树法弥补了代换法猜测困难的缺点,它适于提供"好"的猜测,然后用代换法证明。在递归树中,每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时,递归树的方法尤其有用。
               (4)主方法。也称为主定理,给出求解以下形式的递归式的快速方法,即
               T(n)=aT(n/b)+f(n)
               式中,a≥1和b>1是常数;f(n)是一个渐进的正函数。
   题号导航      2019年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第64题    在手机中做本题