八、算法复杂度初步（共10题）

题目

1. 下面代码段的时间复杂度为（ ）。

int cnt=0;
for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        if((i+j)%3==0) cnt++;

{{ select(1) }}

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

2. 给定算法，时间复杂度为（ ）。

bool f(int arr[], int n, int target) {
    for(int i=0;i<(1<<n);i++){
        int sum=0;
        for(int j=0;j<n;j++)
            if(i&(1<<j)) sum+=arr[j];
        if(sum==target) return true;
    }
    return false;
}

{{ select(2) }}

• O(n^2)
• O(n·2^n)
• O(1)
• O(n^3)

3. 以下代码时间复杂度为（ ）。

int cnt=0;
for(int i=0;i<n;i++)
    for(int j=i;j<n;j++)
        cnt++;

{{ select(3) }}

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

4. 以下代码时间复杂度为（ ）。

int i=1;
while(i<n){
    i*=2;
}

{{ select(4) }}

• O(log n)
• O(n)
• O(n log n)
• O(1)

5. 下面程序段的时间复杂度是（ ）。

for(int i=0;i<n;i++)
    for(int j=0;j<i;j++)
        for(int k=0;k<j;k++)
            cnt++;

{{ select(5) }}

• O(n^3)
• O(n^2)
• O(n)
• O(2^n)

6. 下列算法中，时间复杂度最低的是（ ）。
{{ select(6) }}

• 冒泡排序
• 选择排序
• 二分查找
• 斐波那契递归

7. 对于规模为n的问题，时间复杂度O(2^n)的算法在n=30时通常无法在1秒内完成。（判断题）
{{ select(7) }}

• 正确
• 错误

8. 一个算法的时间复杂度为O(n^2)，那么它一定比O(n log n)的算法慢。（判断题）
{{ select(8) }}

• 正确
• 错误

9. 以下哪个时间复杂度最好？（ ）
{{ select(9) }}

• O(n!)
• O(2^n)
• O(n^2)
• O(log n)

10. 下面代码的时间复杂度是（ ）。

for(int i=0;i<n;i++)
    for(int j=0;j<100;j++)
        cnt++;

{{ select(10) }}

• O(n)
• O(100n)
• O(n^2)
• O(1)