第1节 程序基本常识

1.【NOIP2011】在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指( )。

{{ select(1) }}

• 程序运行时理论上所占的内存空间
• 程序运行时理论上所占的数组空间
• 程序运行时理论上所占的硬盘空间
• 程序源文件理论上所占的硬盘空间

2.【NOIP2013】斐波那契数列的定义如下：$F₁=1,F₂=1,F_n=F_{n-1}+F_{n-2}(n≥3)$。如果用下面的函数计算斐波那契数列的第$n$项，则其时间复杂度为( )。

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

{{ select(2) }}

• $O(1)$
• $O(n)$
• $O(n^2)$
• $O(F_n)$

3.【NOIP2013】T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式T(n)=2*T(n/2)+2n,那么 T(n)=( )。

{{ select(3) }}

• $O(n)$
• $O(n \log n)$
• $O(n²)$
• $O(n²\log n)$

4.【NOIP2015】设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1,

则该算法的时间复杂度为( )。

{{ select(4) }}

• $O(\log n)$
• $O(n \log n)$
• $O(n)$
• $O(n^2)$

5.【NOIP2016】设某算法的时间复杂度函数的递推方程是

$T(n)=2T(\frac{n}{4})+\sqrt{n}$

$T(1)=1$

则该算法的时间复杂度为($\ \ \ \$)。

{{ select(5) }}

• $O(n)$
• $O(\sqrt n)$
• $O(\sqrt n \log n)$
• $O(n^2)$

6.【NOIP2017】假设某算法的计算时间表示为递推关系式

$T(N)=2T(N/2)+N\log N$

T(1)=1

则算法的时间复杂度为()。

{{ select(6) }}

• $O(N)$
• $O(N \log N)$
• $O(N \log ^2N)$
• $O(n²)$

7.【NOIP2012】如果对于所有规模为$n$的输入，一个算法均恰好进行（$\ \ \ \$）次运算，我们可以说该算法的时间复杂度为$O(2^n)$。

{{ select(7) }}

• $2^{n+1}$
• $3^{n}$
• $n*2^n$
• $2^{2n}$