小测验-算法复杂度

1、快速排序最坏情况下的算法时间复杂度为：(2009年真题)

2、基于比较的排序时间复杂度的下限是（ ），其中 $n$ 表示待排序的元素个数。 (2010年普及组) 

3、在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。 (2011年普及组)

4、如果对于所有规模为 $n$ 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 $O($\(2^n\))   (2012年提高组)

5、 (    ）的平均时间复杂度为$O(n\log n)$，其中 $n$ 是待排序的元素个数。

6、斐波那契数列的定义如下：F1​=1, F2​=1, Fn​=Fn−1​+Fn−2​(n≥3)。如果用下面的函数计算斐波那契数列的第 $n$ 项，则其时间复杂度为（ ）。   (2013年提高组)

int F(int n) 
{ 
 if (n <= 2) 
  return 1; 
 else 
  return F(n - 1) + F(n - 2); 
}

7、设某算法的计算时间表示为递推关系式$T(n)=T(n-1)+n$（$n$ 为正整数）及$T(0)=1$，则该算法的时间复杂度为（ ）。 (2014年提高组)

8、$T(n)$ 表示某个算法输入规模为 $n$ 时的运算次数。如果 $T(1)$ 为常数，且有递归式T(n)=2×T(n/2​)+2n，那么 $T(n)=$ （ ）。(2013年提高组)

9、具有 $n$ 个顶点，$e$ 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）  (2014年提高组)

10、以下时间复杂度不是O(n^2)的排序方法是(     )    (2014年提高组)