中国大学算法设计与分析_13期末答案(慕课2023课后作业答案)
74 min read中国大学算法设计与分析_13期末答案(慕课2023课后作业答案)
作业测验
1、考虑下述选择排序算法： 最坏情况下该算法做次交换运算，算法设计这种情况在下列哪种输入条件下发生？
A、分析数列元素各不相等且递增有序
B、期末数列元素各不相等且递减有序
C、慕课数列元素各不相等且无序
D、课后数列所有元素均相等
E、中国作业数列中有相同元素且递增（不减）有序
F、大学答案答案数列中有相同元素且递增（不减）有序
2、算法设计 上述算法所执行的分析加法次数是：
A、
B、期末
C、慕课
D、课后
E、中国作业
F、
3、已知是含有个元素并且从小到大排好序的数组，在中。如果出现在中第个位置的概率是在前一个位置概率的一半，当充分大时，下述查找算法平均情况下的时间复杂度（ ）。（只需给出近似值）
A、2
B、3
C、4
D、1
E、
F、
G、
4、下列哪个排序算法在最坏情况下的时间复杂度最低？
A、插入排序
B、堆排序
C、冒泡排序
D、快速排序
5、下列有关阶乘函数的表述错误的是？
A、
B、
C、
D、
E、
6、与之间的渐近关系是？
A、
B、
C、
D、无法确定
7、以下关于函数阶的关系中，哪几项是正确的？
A、
B、
C、
D、
E、
F、
8、下表给出组和函数， 使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")
9、下表给出组和函数， 使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")
10、下表给出组和函数， 使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")
第二周 基础知识（2）：序列求和方法，递推方程求解
作业测验
1、递归方程的解的精确值是：
A、
B、
C、
D、
E、
F、
2、，的阶是：
A、
B、
C、
D、
E、
F、
3、请用主定理确定递归式的渐近的界：
A、
B、
C、
D、
E、
4、给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。 假设对于个数的数组，在最坏情况下算法A的比较次数是，该算法在最坏情况下的递推方程是：
A、
B、
C、
D、
E、
F、
5、给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。 假设对于个数的数组，在最坏情况下算法A的比较次数是，则的精确值是？
A、
B、
C、
D、
E、
F、
6、把插入排序算法加以改进，可以得到二分插入排序算法。设输入数组是，插入排序算法的基本操作是：假定的前个数已经排好，将插入。插入时从开始，顺序检查，直到找到插入的合适的位置，将它插入。改进插入排序算法的步骤是：插入的操作不是在中从后向前顺序检索，而是采用二分检索方法找到插入的正确位置。 如果输入规模是，该算法在最坏情况下的比较次数是，那么该算法在最坏情况下的递推方程是
A、
B、
C、
D、
E、
7、把插入排序算法加以改进，可以得到二分插入排序算法。设输入数组是，插入排序算法的基本操作是：假定的前个数已经排好，将插入。插入时从开始，顺序检查，直到找到插入的合适的位置，将它插入。改进插入排序算法的步骤是：插入的操作不是在中从后向前顺序检索，而是采用二分检索方法找到插入的正确位置。 如果输入规模是，该算法在最坏情况下的比较次数是，那么该算法在最坏情况下的递推方程的解是？
A、
B、
C、
D、
E、
F、
8、设递推方程给出了算法A在最坏情况下的时间复杂度函数，算法B在最坏情况下的时间复杂度函数满足递推方程，那么要使算法B比算法A具有更高的效率，即时间复杂度的阶低于的阶的最大正整数的值为：
9、给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。 假设对于个数的数组，在最坏情况下算法A的比较次数是，则的初值是（ ）？
10、把插入排序算法加以改进，可以得到二分插入排序算法。设输入数组是，插入排序算法的基本操作是：假定的前个数已经排好，将插入。插入时从开始，顺序检查，直到找到插入的合适的位置，将它插入。改进插入排序算法的步骤是：插入的操作不是在中从后向前顺序检索，而是采用二分检索方法找到插入的正确位置。 如果输入规模是，该算法在最坏情况下的比较次数是，那么该算法在最坏情况下的递推方程的初值是（ ）？
第三周 分治策略（1）
作业测验
1、双Hanoi塔问题是Hanoi塔问题的一种推广，与Hanoi塔的不同点在于：2n个圆盘，分成大小不同的n对，每对圆盘完全相同。初始，这些圆盘按照从大到小的次序从下到上放在A柱上，最终要把它们全部移到C柱，移动的规则与Hanoi塔相同。BiHanoi(A, C, n)的功能是从A移动2n个盘子到C，其中BiMove(A, C)表示从A移动两个盘子到C。下列哪一段代码是利用分治策略给出的正确的移动策略：
A、
B、
C、
D、
2、给定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从大到小的次序输出，现有如下算法， 算法：调用i次找最大算法Findmax，每次从S中删除一个最大的数。该算法在最坏情况下的时间复杂度是：
A、
B、
C、
D、
E、
3、给定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从大到小的次序输出，现有如下算法， 算法：对S排序，并输出S中最大的i个数。该算法在最坏情况下的时间复杂度是：
A、
B、
C、
D、
E、
F、
4、有n个砝码（其中n为2的幂，即），每个重g克，其中一个不合格(重量可能大于或小于g克). 有一个秤可以称出重物的准确重量. 假设所有的砝码可以同时放到秤上，设计一个算法找出这个不合格的砝码，且秤重的次数达到最少. 采用分治算法，每次取一半砝码（比如t个）称重，如果恰好重tg克，那么不合格的砝码在剩下的砝码中；否则不合格的砝码就在被称重的砝码中. 设n枚砝码的称重次数是T(n)，关于T(n)的递推方程是:T(n)=T( ) + 1 括号里应该填：
A、
B、
C、
D、
E、
5、在之前n个砝码的题目中（其顺序可能出现在该题之后），在初值T(2)=1条件下，确定：对于给定的n个砝码，找到其中不合格砝码最多需要称重多少次，并选择一个函数填入括号内. T(n)=( )
A、
B、
C、
D、
E、
6、设问题P的输入规模是n，下述三个算法是求解P的不同的分治算法. 算法1：在常数时间将原问题划分为规模减半的5个子问题，递归求解每个子问题，最多用线性时间将子问题的解综合而得到原问题的解. 算法2：先递归求解2个规模为n-1的子问题，最多用常量时间将子问题的解综合得到原问题的解. 算法3：在常数时间将原问题划分为规模n/3的9个子问题，递归求解每个子问题，最多用时间将子问题的解综合得到原问题的解. 要求在上述三个算法中选择最坏情况下时间复杂度最低的算法，需要选择哪个算法？
A、1
B、2
C、3
D、都不对
7、设问题P的输入规模是n，下述三个算法是求解P的不同的分治算法. 算法1：在常数时间将原问题划分为规模减半的5个子问题，递归求解每个子问题，最多用线性时间将子问题的解综合而得到原问题的解. 算法2：先递归求解2个规模为n-1的子问题，最多用常量时间将子问题的解综合得到原问题的解. 算法3：在常数时间将原问题划分为规模n/3的9个子问题，递归求解每个子问题，最多用时间将子问题的解综合得到原问题的解. 设最坏情况下时间复杂度最低的算法为A，A在最坏情况下的时间复杂度是( )
A、
B、
C、
D、
E、
第四周 分治策略（2）
作业测验
1、给定含有 个不同的数的数组 。如果 中存在 ，则称 是单峰的，并称 是 的“峰顶”。假设 是单峰的，请把 a - d 四行代码补全到算法中使得算法正确找到 的峰顶。 。
A、d, c, a, b
B、d, c, b, a
C、c, d, b, a
D、d, b, c, a
E、d, a, b, c
2、设信号向量是 ， ，用于平滑处理的权向量是，根据卷积计算公式，处理后的信号向量是，那么的值分别为( )，从下面的项中选择合适的答案：
A、4.1，5.8，5.5
B、2.2，8.4，3.2
C、4.7，4.3，7.7
D、0.4，3.2，0.6
3、在枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重)，如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是一个算法找出这枚不合格的硬币，每称1次作为1次基本运算。请把a,b,c三行代码填到算法中正确的位置中。
A、c, a, b
B、c, b, a
C、a, b, c
D、b, a, c
E、b, c, a
4、设 T是n个不等的数构成的数组，现在用分治算法找T的最大数. 先把T从中间划分成两个大小差不多的子数组和，递归地求和的最大数，分别记作和. 比较和，那么输出就是. 以元素比较做基本运算，该算法在最坏情况下的时间复杂度的的递推方程是：
A、
B、
C、
D、
5、找第k小问题的分治算法. 算法开始将n个数分成5个1组，共个组，然后取每组的中位数构成集合M，递归利用找第k小算法，计算M的中位数，用作为标准划分数组，得到子问题和. 递归求解其中一个子问题即可. 如果开始分组时是3个元素一组，算法在最坏情况下的时间复杂度将达到，如果开始分组时取7个元素一组，那么用划分数组后产生的子问题最大规模将达到（ ），算法在最坏情况下的时间复杂度是（ ），两个括号里分别应该填：
A、
B、
C、
D、
6、 针对表1给定的六个算法的时间复杂度T(n)，从表2中选择关于T(n)的正确的递推方程，并将方程所对应的标号a,b,c,d,e,f按照算法一、二、三、四、五、六的顺序填入括号内（填写时6个字母之间不要加任何符号）。
7、 针对表1给定的六个算法的时间复杂度T(n)，从表2中选择关于T(n)的正确的递推方程，从表3中选择正确的解，并将解所对应的标号1,2,3,4,5按照算法一、二、三、四、五、六的顺序填入括号内（填写时6个数字之间不要加任何符号）.
第五周 动态规划（1）
作业测验
1、考虑考虑矩阵链相乘问题，假设给定的输入实例是, 根据动态规划算法，备忘录中的等于
A、60000
B、36000
C、3000
D、30000
E、3000
2、设是n个不等的整数构成的序列，A的一个单调递增子序列是序列使得，且。子序列的长度是含有的整数个数k。例如，它的长度为4的递增子序列是：或，请使用动态规划算法求A的一个最长的单调递增子序列。设表示以作为最后项的最长单调递增子序列的长度，那么，如果在前面有项使得 如果，那么一定有：
A、或者是序列A的第一个数，或者它前面的数都比它大
B、是序列A的第一个数
C、前面有数，且
D、前面的数都大于
3、在第2题中，设算法输入的实例是A=<2,8,4,-4,5,9,11>，那么 的值是：
A、1, 2, 2, 1, 3, 3, 5
B、1, 2, 2, 0, 3, 4, 5
C、1, 2, 2, 1, 3, 4, 5
D、1, 2, 1, 2, 2, 3, 4
4、设有n项任务，加工时间分别表示为正整数。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令，那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。 假设问题的解是，其中0或1. 如果，那么第i项任务放到第一台机器上加工；如果，那么第i项任务放到第二台机器上加工。把这个问题描述成组合优化问题，那么它的目标函数是：
A、
B、0或者1, i=1,2,3,...,n
C、
D、
5、在第4题中，从问题本质看，任务的加工时间相当于0-1背包问题中的下述输入参数：
A、既是物品i的价值，也是它的重量
B、仅代表物品i的价值
C、仅代表物品i的重量
D、物品i单位重量的价值
6、考虑上述双机调度问题.令表示考虑前k项任务，在第一台机器时间不超过y的情况下其加工时间的最大值. 那么
A、
B、
C、
D、
7、在第6题中，给定双机调度问题的实例如下： 假设第一条机器的完成时间不超过T，那么该实例有______个解
A、0
B、1
C、2
D、3
E、4
8、一个有向图D由顶点集V和边集E构成。如果D有n个顶点，那么顶点集为，如果在D中从到有一条有向边，那么属于E。有向图D可以用一个n行n列的0-1矩阵M来表示。如果D中的到有一条有向边，那么矩阵M的第i行第j列元素；否则。图的连通性是指从图的某些顶点到其他顶点存在一条由连续有向边构成的路径。一个著名的检查图的连通性的算法就是Warshall算法。假设M是图D的矩阵表示，考虑n+1个矩阵构成的序列将矩阵的i行j列元素记作。对于当且仅当图中存在一条从到的路径，并且这条路径除端点外中间只经过中的顶点。不难看出就是M，而在中如果，则说明D中和是连通的。Warshall算法从开始，顺序计算,直到为止。可以通过动态规划的迭代实现Warshall算法，用以下实例作为输入，给出实例的结果。假设某有向网络的结点是a,b,c,d，已知网络的矩阵表示是：
A、a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
B、a 可以连通到 b,c,d;b 可以连通到 c;c 可以连通到 d;d 可以连通到 c
C、a 可以连通到 b,c;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
D、a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 b,d;d 可以连通到 c
第六周 动态规划（2）
作业测验
1、设P是一台Internet上的Web服务器。是n个下载请求的集合，表示下载请求i所申请的带宽。已知服务器的最大带宽是正整数K。我们的目标是使带宽得到最大限度的利用，即确定T的一个子集S，使得，且的值达到最小。类似于0-1背包问题，令表示考虑前i个申请，带宽限制为y时的最大带宽使用量，则有如下递推式：
A、d,a,c,b,d
B、d,a,b,b,c
C、c,b,c,b,d
D、c,a,b,a,d
E、c,a,b,b,d
2、找零钱问题： 设有面值为的n种货币，需要付款的总钱数为M，其中和M都是正整数。问如何付款使得所付货币张数最少？ 设分别表示付款时使用第i种货币的张数，用组合最优化方法描述该问题，约束条件是 ，其中 定义函数表示使用前k种币值总钱数为y时所使用钱币的最少张数, 定义函数表示使用后k种币值总钱数为y时所使用钱币的最少张数, 那么该问题的目标函数是：
A、
B、
C、
D、
3、考虑找零钱问题, 设表示使用前k种币值总钱数为y时所使用钱币的最少张数，则 横线上应该填：
A、
B、
C、
D、
E、
4、第4题中所给的算法的时间复杂度是：
A、
B、
C、
D、
E、
5、二维0-1背包问题：给定n种物品和一个背包。物品i的重量是，体积是，价值为，每种物品只有1个。背包的重量限制为W，容积限制为V。问如何选择装入背包的物品，使得背包物品的总价值最大？ 设表示使用前i种物品、背包重量限制为j、容积为k时的最大价值，其中 那么递推方程是：
A、
B、
C、
D、
6、考虑上述第6题中的二维0-1背包问题，动态规划算法的时间复杂度是：
A、
B、
C、
D、
E、
7、有正实数构成的数字三角形排列形式如图所示. 第一行的数为；第二行的数从左到右依次为第n行的数为.从开始，每一行的数只有两条边可以分别通向下一行的两个数和. 用动态规划算法找出一条从向下通到中某个数的路经，使得该路经上的数之和达到最大. 令是从到的路径上的数的最大和，则
A、
B、
C、
D、
8、第8题中所述算法的时间复杂度是：
A、
B、
C、
D、
E、
9、用动态规划算法求解和的一个最长公共子序列（LCS），标记函数的表B[i,j]如下表所示： 该实例的解是(顺序从前到后给出最长公共子序列的字符,字符之间不要加任何符号)
第七周 贪心法（1）
作业测验
1、设有n个顾客同时等待一项服务，顾客i需要的服务时间为。从时刻0开始安排服务。一个顾客的等待时间从时刻0开始计时，直到完成对他服务的时刻为止。问应该怎样安排n个顾客的服务次序使得总的等待时间（每个顾客等待时间的总和）最少？ 针对以上问题，请补全下面贪心算法： 横线上分别应该填：
A、
B、
C、
D、
2、在第一题中，如果安排服务的顺序是其中是的某个排列，那么总的等待时间是：
A、
B、
C、
D、
E、
3、第一题中算法最坏情况下的时间复杂度为：
A、
B、
C、
D、
E、
4、设有一条边远山区的道路AB，沿着道路AB分布着n所房子。这些房子到A的距离分别是。为了给所有房子的用户提供移动电话服务，需要在这条道路上设置一些基站。为了保证通信质量，每所房子应该位于距离某个基站4km范围之内。设计一个算法找到基站的位置，并且使得基站总数达到最少。下面哪一个算法可以得出正确的解：
A、
B、
C、
D、
5、有n个进程。对于进程i的开始时间为，截止时间为。可以通过监测程序Test来测试正在运行的进程。Test每次测试时间很短，可以忽略不计。换句话说，如果Test在时刻t进行测试，那么它将对满足的所有进程同时取得测试数据。假设最早运行的进程的开始时间是0，问：如何安排测试时刻，使得对每个进程至少测试一次，且Test测试的次数达到最少？请补全下面贪心算法。
A、
B、
C、
D、
E、
6、有n个文件存在磁带上，从单元1开始存储，每个文件占用连续的空间。已知第i个文件需要的存储空间为，被检索的概率是且检索每个文件需要从磁带的开始位置进行操作，例如文件i存储在磁带的第100到第250单元，那么检索该文件需要的时间是250。假设n个文件的排列顺序是以扫描单元数作为时间复杂度的度量，这些文件的平均检索时间是：
A、
B、
C、
D、
7、用贪心法求解上述文件检索问题，贪心策略是：
A、按照比值从大到小对文件重新排序为，然后按照的顺序将文件存入磁带
B、按照文件被检索的概率从大到小对文件重新排序为，然后按照的顺序将文件存入磁带
C、按照文件被检索的概率从大到小对文件重新排序为，然后按照的顺序将文件存入磁带
D、按照乘积从大到小对文件重新排序为然后按照的顺序将文件存入磁带
第八周 贪心法（2）
单元作业
1、1、给定数轴X上n个不同点的集合{ x1,x2,...,xn} , 其中x1<x2<?<xn 。现在用若干个长度为1的闭区间来覆盖这些点。设计一个算法找到最少的闭区间个数和位置。 要求如下： (1) 请简要叙述贪心算法的策略；（2分） (2) 请证明你的贪心策略能够给出最优解（4分）； (3) 请分析算法的空间和时间复杂度（4分）。 (请用格式为pdf的附件提交题目解答)
2、2、一个公司需要购买n个密码软件的许可证，按规定每个月至多可得到一个软件许可证. 每个许可证当前售价都是1000元，但是第i个许可证的售价将按照ri>1的指数因子增长，i=1,2,...,n. 例如，第i个许可证的售价在1个月后将是ri?1000元，2个月后将是r2i?1000元，k个月后将是rki?1000元. 假设r1,r2,…,rn是给定正整数，试给出一个购买许可证的顺序，以使得花费的总钱数最少. 1. 令问题的解I是i1,i2,…,in，其中i1,i2,…,in是的排列。问：按照这个解给出的顺序，当月购买第一个许可证，以后每个月恰好购买一个软件许可证，总的花费是多少元？ (2分) 2. 设计一个贪心算法求解这个问题，用一段简短的话说明该算法的贪心策略.(2分) 3. 证明算法的正确性. （4分） 4. 求出算法在最坏情况下的时间复杂度. （2分） (请用格式为pdf的附件提交题目解答)
第九周 回溯与分支限界（1）
作业测试
1、最小重量机器设计问题。某设备需要4种配件，每种1件，有3个供应商提供这些配件，下面表格给出相关的价格和每种配件的重量。从中选择4种配件，使得总价值不超过120，总重量最轻。 使用回溯算法，该问题的解为4维向量 ，其中xi代表第i个零件的供应商标号。该问题的搜索空间是
A、排列树
B、3叉树
C、子集树
D、4叉树
2、在上述最小重量机器设计问题中，如果用回溯算法在搜索树中以深度优先顺序搜索，此刻到达部分向量所代表的结点，在该处下一个分量的可取值范围是
A、{ 1，2，3}
B、{ 1}
C、{ 1，2}
D、{ 4}
3、应用回溯算法，给出的所有置换。该问题的解向量是，那么该搜索空间是( ), 有( )片树叶。
A、子集树，2n
B、排列树，（n-1）！
C、排列树，n！
D、子集树，2^n
4、在上述生成的所有置换的问题中，在搜索树的结点处，的取值范围（ ）。
A、
B、
C、
D、
5、子集和问题。设n个不同的正数构成集合S，求出使得和为某数M的S的所有子集。用回溯法求解，设，问题为求S满足条件的所有子集A。解向量为，其中当且仅当 。搜索空间为子集树。部分向量表示已经考虑了对的选择。此刻已经选入子集A的数之和B(k)是满足：
A、
B、
C、
D、
6、针对上述子集和问题，假设回溯算法搜索到部分向量表示的结点，继续搜索以该结点为根的子树的条件是：
A、
B、
C、
D、
7、上述子集和的回溯算法最坏情况下的时间复杂度是：
A、
B、
C、
D、
8、p { margin-bottom: 0.1in; line-height: 120%; } 在上述最小重量机器设计问题中，如果用回溯算法，编号为1，2，3，4的零件分别应选择的供应商编号为： （请直接填写数字，不包含任何其他符号，例如选择的供应商为1,2,3,1，则填写1231）
第十周 回溯与分支限界
作业测试
1、分派问题。给 n 个人分配 n 件工作,给第 i 个人分配第 j 件工作的成本是，试求成本最小的工作分配方案。 设n个人的集合是，n项工作的集合是，每个人恰好1项工作，表示把工作j分配给i，其中。解向量，分配成本是。搜索空间是排列树。部分向量表示已经考虑了对人的工作分配。那么在这个部分向量对应节点分支的约束条件为：
A、
B、
C、
D、
2、针对上题中有下面几个代价函数，哪一个是合理的？
A、
B、
C、
D、
3、上述回溯算法最坏情况下的时间复杂度是：
A、
B、
C、
D、
4、哨兵布置问题。一个博物馆由排成个矩形阵列的陈列室组成，需要在陈列室中设立哨位，每个哨位上的哨兵除了可以监视自己所在陈列室外，还可以监视他上、下、左、右四个陈列室。试给出一个最佳哨位安排方法，使得所有陈列室都在监视之下，但使用的哨兵最少。本题的解是一个的0-1矩阵X,当且仅当陈列室有哨兵，其中初始令所有的。算法从开始直到(m, n)为止,搜索树是二叉树,有m × n层。 每个节点对应一个陈列室。如果令X[i, j] = 0,表示取消(i, j)位置的哨兵,进入左子树;否则进入右子树。在进入左子树时需要检查房间被监视的情况,即检查此位置以及上下左右位置是否被监视。下列哪种情况出现时,应该继续左分支的搜索:
A、(i, j)上下左右位置的房间不被监视,其他所有房间都被监视
B、(i, j)及其上下左右位置的房间都被监视
C、(i, j)以及上下左右位置房间中某个房间不被监视,其他所有房间都被监视
D、(i, j)房间不被监视,其他所有房间都被监视
5、上题算法最坏情况下的时间复杂度是:
A、
B、
C、
D、
6、有载重量为 M 的背包,n 种物品的重量及价值分别。如果每个物品只有一件,求一种最优装法,使得装入背包的物体价值最大。考虑回溯算法。先对物品按照从大到小进行排序,并用序列< 重量,价值 >来表示排好序以后的物品序列。对如下给定实例: 排序后的结果是: 用 =1或 0来分别表示取用或者不用物品 i。那么在搜索树的节点处的代价函数为:
A、
B、
C、
D、
7、上题中,假设物品数量为 n,背包载重为 M,那么算法最坏情况下的时间复杂度是:
A、
B、
C、
D、
8、有n个操作员,n项作业,已知第i项作业分配给第j个操作员的加工时间为。如果所有操作员都从时刻 0 开始工作,最后一项作业完成的时刻记作全部作业的完成时间。问如何分配作业使得全部作业的完成时间最短?下表是一个 n=4 的实例,其中第 j 行的 4 个数据分别表示第 j 位操作员完成 4 项作业所需时间,j=1, 2, 3, 4。 这是一个组合优化问题。问题的解是向量，其中表示第 i 项作业分配给操作者。搜索树是一棵 n 叉树。在搜索树的结点,完成已分配作业 1,2,...,k 需要占用的时间为:
A、
B、
C、
D、
9、上题中,假设操作员数量和作业数量都是 n,那么算法的最坏情况下时间复杂度是:
A、
B、
C、
D、
学习通算法设计与分析_13
本篇文章主要介绍算法复杂度分析的相关知识。
算法复杂度
算法复杂度是指算法的时间复杂度和空间复杂度。时间复杂度是指算法执行时间的增长速度，通常用 Big O 表示；空间复杂度是指算法需要占用的内存空间，通常用 Big O 表示。
时间复杂度的计算方法
计算时间复杂度的方法有多种，常用的有以下几种：
- 计算每行代码的执行次数，然后相加得到总的执行次数。
- 使用常见算法的时间复杂度公式，如循环、递归等。
- 建立递推式，然后求解递推式的解析式。
其中，第一种方法适用于代码比较简单、逻辑比较清晰的情况；第二种方法适用于常见算法的情况，如冒泡排序、归并排序等；第三种方法适用于复杂算法的情况，如动态规划、贪心算法等。
时间复杂度的常见表示方法
时间复杂度的常见表示方法有以下几种：
- 常数复杂度：O(1)
- 线性复杂度：O(n)
- 对数复杂度：O(log n)
- 平方复杂度：O(n^2)
- 立方复杂度：O(n^3)
- 指数复杂度：O(2^n)
其中，常数复杂度表示算法的执行时间不随数据规模的增加而增加，例如赋值、加减乘除等简单操作；线性复杂度表示算法的执行时间与数据规模成线性关系，例如遍历数组、查找某个元素等；对数复杂度表示算法的执行时间随数据规模的增加而增加，但增长速度很慢，例如二分查找；平方复杂度表示算法的执行时间与数据规模的平方成正比，例如冒泡排序、选择排序等；立方复杂度表示算法的执行时间与数据规模的立方成正比，例如插入排序；指数复杂度表示算法的执行时间随数据规模的增加呈指数增长，例如背包问题、旅行商问题等。
空间复杂度的计算方法
计算空间复杂度的方法比较简单，只需要统计算法使用的额外空间即可。通常，空间复杂度的计算方法与时间复杂度的计算方法类似，都是通过计算每行代码的执行次数，然后相加得到总的空间复杂度。
空间复杂度的常见表示方法
空间复杂度的常见表示方法与时间复杂度类似，通常用 Big O 表示。
总结
算法复杂度是衡量算法效率的重要指标，计算方法和表示方法较为简单，但是对于复杂算法的计算和表示需要更深入的学习和理解。
