信息学奥赛-提高级 题库
递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度,该算法的时间复杂度是多少?
用主定理或递归树法。递归树中:
第1层总时间复杂度n2;
第2层2*(n/2)2=n2/2;
第3层4*(n/4)2=n2/4;
……总和为n2*(1+1/2+1/4+…)≤2n2,时间复杂度为O(n2)。
斐波那契数列定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2),使用朴素递归方法计算F(n)的时间复杂度是指数级的,而使用动态规划(或迭代)方法的时间复杂度是线性的,造成这种差异的根本原因是?
朴素递归会重复计算大量重叠子问题(如计算F(5)需算F(4)和F(3),算F(4)又需算F(3)和F(2)),动态规划通过存储子问题结果避免重复计算。
记程序结束前p数组元素的最大值为P,则该代码的时间复杂度是?
假设一个长度为n的整数数组中每个元素互不相同,且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?( )
在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对,表的装载因子为α(0<α≤1)。在使用开放地址法解决冲突的过程中,最坏情况下查找一个元素的时间复杂度为( )?
开放地址法当计算出来的地址被占用时,用再寻址的方法寻找下一个地址,如果还是占用就接着寻找,直到找到一个空的地址,在最坏情况下可能会遍历所有已经占用的地址
假设n是图的顶点的个数,m是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于m=θ(n)的稀疏图而言,下面的四个选项,哪一项的渐近时间复杂度最小
由于图片,m和n的增长速度完全相同,可以认为图片,C为常数。把所有m替换成n后很容易排除B、C选项。考虑另外两个选项,当x比较大时,一定有图片,同理图片,两边同乘图片得到图片,而常数不影响渐进时间复杂度,说明A比D小。
现在用如下代码来计算下xn,其时间复杂度为()
虽然看上去使用了快速幂,但是每次分治后程序把quick_power运行了两次,没能真正实现分治法,复杂度仍然是O(n)。
.solve1(n)的时间复杂度为()。
设a数组中最大值减最小值加1为A,则f函数的时间复杂度为()。
考虑对 n 个数进行排序,以下最坏时间复杂度低于 O(n^2)的排序方法是( )。
对于给定的 n,分析以下代码段对应的时间复杂度,其中最为准确的时间复杂度为( )。
int i, j, k = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j*=2) {
k = k + n / 2;
}
}
该算法最坏情况下的时间复杂度为( )。
斐波那契数列的定义为:F1=1,F2=1,Fn=Fn-1+Fn-2 (n>=3)。现在用如下程序来计算斐波那契数列的第 n 项,其时间复杂度为( )。
F(n):
if n<=2 return 1
else return F(n-1) + F(n-2)
O(n2)
O(2n)
solve1(1, n) 的时间复杂度为( )。
Θ(n)
Θ(n log n)
solve2(1, n) 的时间复杂度为( )。
设输入字符串长度为 n,encode 函数的时间复杂度为( )。
具有n个顶点,e条边的图釆用邻接表存储结构,进行深度优先遍历运算的 时间复杂度为()
对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为()。
(2.5分)若输入的d[i]为i,此程序①平均的时间复杂度和②最坏 情况下的时间复杂度分别是()