在n加倍的情况下，一个O(n2)的算法计算时间增长______倍。

在n加倍的情况下，一个O（n2)的算法计算时间增长______倍。

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“在n加倍的情况下，一个O(n2)的算法计算时间增长_____…”相关的问题

第1题

设计一个O（n²)时间的算法,找出由n个数组成的序列的最长单调递增子序列.

点击查看答案

第2题

问题描述:给定两个n×n矩阵A和B,试设计一个判定A和B是否互逆的蒙特卡罗算法（算法的计算时间应为

问题描述:给定两个n×n矩阵A和B,试设计一个判定A和B是否互逆的蒙特卡罗算法(算法的计算时间应为O(n²).

算法设计:设计一个蒙特卡罗算法,对于给定的矩阵A和B,判定其是否互逆.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示矩阵A和B为n×n矩阵.接下来的2n行,每行有n个实数,分别表示矩阵A和B中的元素.

结果输出:将计算结果输出到文件output.txt.若矩阵A和B互逆,则输出“YES",否则输出“NO".

点击查看答案

第3题

假定序列中n个元素的数值为独立均匀地随机分布，试证明：a)列表的插入排序算法平均需做约n²/4=o（n²)次元素比较操作;b)向量的插入排序算法平均需做约n²/4=o（n²)次元素移动操作;c)序列的插入排序算法过程中平均有expected-o（logn)个元素无需移动。

点击查看答案

第4题

用二分查找法对具有n个结点的线性表查找一个结点，所需的平均比较次数为（）。

A.O（n2）

B.O（nlog2n）

C.O（n）

D.O（log2n）

点击查看答案

第5题

设二叉树共含n个节点，且各节点数据项的类型支持大小比较（类似于整数或浮点数)。试设计并实现一个递归算法，在o（n)时间内将每个节点的数值替换为其后代中的最大数值。

点击查看答案

第6题

考查教材42页代码2.14中的无序向量唯一化算法deduplicate（)。a)试证明，即便在最好情况下，该算法也需要运行Ω（n²)时间;b)试参照教材46页代码2.19中有序向量唯一化算法uniquify（)的技巧，改进该算法，并分析其时间复杂度;c)试继续改进该算法，使其时间复杂度降至0（nlogn);d)这一效率是否还有改进的余地？为什么？

点击查看答案

第7题

设A[0，n)[0，n)为整数矩阵（即二维向量)，A[0][0]=0且任何一行（列)都严格递增。a)试设计一个算法，对于任一整数x≥0，在o（r+s+logn)时间内，从该矩阵中找出并报告所有值为x的元素（的位置)，其中A[0][r]（A[s][0])为第0行（列)中不大于x的最大者;b)若A的各行（列)只是非减（而不是严格递增)，你的算法需做何调整？复杂度有何变化？

点击查看答案

第8题

设G=（V,E)是源为s,汇为t,且容量均为整数的一个流网络.已知f是G的一个最大流.①假设一条边（u,v)∈E的容量增1,试设计在O（V|+|E|)时间内更新最大流f的算法.②假设一条边（u,v)∈E的容量减1,试设计在O（V|+|E|)时间内更新最大流f的算法.

点击查看答案

第9题

在附加某些特定条件之后，问题的难度往往会有实质的下降。比如，若待编码字符集已按出现频率排序，

则Huffman编码可以更快完成。在编码过程中，始终将森林