时间复杂度分析（共 15 题）

单选题

1. 若某算法满足递推式：T(n) = 2T(n/2) + O(n)，则其时间复杂度为（ ）。
   {{ select(1) }}

• O(n)
• O(n log n)
• O(n²)
• O(log n)

2. 下面代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）。

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

   {{ select(2) }}

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

3. 下面代码实现了分治求“最大连续子段和”，其时间复杂度为（ ）。

   int solve(vector<int>& a, int l, int r) {
       if (l == r) return a[l];
       int mid = (l+r)/2;
       int left = solve(a, l, mid);
       int right = solve(a, mid+1, r);
       int sum = 0, lmax = INT_MIN;
       for (int i = mid; i >= l; i--) { sum += a[i]; lmax = max(lmax, sum); }
       sum = 0; int rmax = INT_MIN;
       for (int i = mid+1; i <= r; i++) { sum += a[i]; rmax = max(rmax, sum); }
       return max({left, right, lmax+rmax});
   }
   

   {{ select(3) }}

• O(n²)
• O(n log n)
• O(log n)
• O(n)

4. 下面 C++ 代码用于求斐波那契数列，函数 fiboA() 和 fiboB() 的时间复杂度分别是（ ）。

   int fiboA(int N) {
       if (N == 1 || N == 2) return 1;
       return fiboA(N-1) + fiboA(N-2);
   }
   int fiboB(int N) {
       if (N == 1 || N == 2) return 1;
       int last2 = 1, last1 = 1, nowVal = 0;
       for (int i = 2; i < N; i++) {
           nowVal = last1 + last2;
           last2 = last1;
           last1 = nowVal;
       }
       return nowVal;
   }
   

   {{ select(4) }}

• O(2^n) 和 O(n)
• O(n) 和 O(2^n)
• O(n) 和 O(n)
• O(2^n) 和 O(2^n)

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

   int sum = 0;
   for (int i = 1; i <= n; i++)
       for (int j = i; j <= n; j++)
           sum += a[i][j];
   

   {{ select(5) }}

• O(n)
• O(n log n)
• O(n²)
• O(n³)

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

   for (int i = 1; i <= n; i *= 2) {
       for (int j = 1; j <= n; j++) {
           // O(1) operation
       }
   }
   

   {{ select(6) }}

• O(n)
• O(n log n)
• O(n²)
• O(log n)

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

   for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= i; j++) {
           for (int k = 1; k <= 100; k++) {
               // O(1) operation
           }
       }
   }
   

   {{ select(7) }}

• O(n)
• O(n²)
• O(n³)
• O(100n²) 但常数忽略，仍为 O(n²)

8. 下面函数的时间复杂度是（ ）。

   double quick_power(double x, unsigned n) {
       if (n == 0) return 1;
       if (n == 1) return x;
       return quick_power(x, n/2) * quick_power(x, n/2) * ((n & 1) ? x : 1);
   }
   

   {{ select(8) }}

• O(n)
• O(n²)
• O(log n)
• O(n log n)

9. 假设数组 a 的值域范围是 D，以下程序的时间复杂度是（ ）。

   bool check(int n, int a[], int k, int dist) { ... }
   int solve(int n, int a[], int k) {
       std::sort(a, a + n);
       int l = 0, r = a[n-1] - a[0];
       while (l < r) {
           int mid = (l + r + 1) / 2;
           if (check(n, a, k, mid)) l = mid;
           else r = mid - 1;
       }
       return l;
   }
   

   {{ select(9) }}

• O(n log n + n log D)
• O(n log n)
• O(n log D)
• O(n²)

10. 下面代码实现素数表的线性筛法，其时间复杂度是（ ）。

    vector<int> linear_sieve(int n) {
        vector<bool> is_prime(n + 1, true);
        vector<int> primes;
        for (int i = 2; i <= n; ++i) {
            if (is_prime[i]) primes.push_back(i);
            for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
                is_prime[i * primes[j]] = false;
                if (i % primes[j] == 0) break;
            }
        }
        return primes;
    }
    

    {{ select(10) }}

• O(n)
• O(n log log n)
• O(n log n)
• O(n²)

判断题

11. 若某算法满足递推式 T(n) = 2T(n/2) + O(n)，则其时间复杂度为 O(n log n)。
    {{ select(11) }}

• 正确
• 错误

12. 快速排序的时间复杂度总是比插入排序的时间复杂度低。
    {{ select(12) }}

• 正确
• 错误

13. 归并排序的时间复杂度在最好、最坏和平均情况下均为 O(n log n)。
    {{ select(13) }}

• 正确
• 错误

14. 二分查找的时间复杂度是 O(log n)。
    {{ select(14) }}

• 正确
• 错误

15. 下面代码的时间复杂度是 O(n²)。

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j += i + 1)
            // O(1)
    

    {{ select(15) }}

• 正确
• 错误