信息学奥赛-提高级 题库
(2.5分)若输入的d[i]都为同一个数,此程序平均的时间复杂度是()
(3分)若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )。
设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n(n 为正整数)及T(0) = 1,则该算法的时间复杂度为( )。
O(log n)
O(n log n)
O(n)
O(n2)
若某算法的计算时间表示为递推关系式:
T(N)=,2T(N/2)+N log N
T(1)=1
则该算法的时间复杂度为( )。
p(N)
O(Nlog N)
O(Nlog2N)
O(N2)
设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n(n 为正整数)及 T(0) = 1,则该算法的时间复杂度为( )。
具有n个顶点,e条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运算的时间复杂度均为( )。
斐波那契数列的定义如下:F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果用下面的函数计算斐波那契数列的第 n 项,则其时间复杂度为( )。
int F(int n)
{
if(n<=2)
return 1;
else
return F(n-1)+F(n-2);
}
对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为( )。
在使用高级语言编写程序时,一般提到的“空间复杂度”中的空间是指( )。
应用快速排序的分治思想,可以实现一个求第 K 大数的程序。假定不考虑极端的最坏情况,理论上可以实现的最低的算法时间复杂度为( )。
具有n个顶点,e条边的图釆用邻接表存储结构,进行深度优先遍历运算的 时间复杂度为()
对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为()。
(2.5分)若输入的d[i]为i,此程序①平均的时间复杂度和②最坏 情况下的时间复杂度分别是()
(2.5分)若输入的d[i]都为同一个数,此程序平均的时间复杂度是()
考虑对 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;
}
}