CSP-S 复习卷 S01 · 复杂度分析

已知算法运行时间 $T(n) = O(n^2)$。下列解释正确的是？

将下列复杂度按增长速度从小到大排列，正确的是？

对存放在连续内存中的 int a[100000]，执行 a[52345] = 7; 所需时间与数组大小 n 的关系是？

以下代码片段的时间复杂度是？

01for (int i = 0; i < n; i++) sum++;

以下代码的时间复杂度是？

01for (int i = 0; i < n; i++)
02    for (int j = 0; j < n; j++)
03        sum++;

以下代码的时间复杂度是？

01for (int i = 1; i <= n; i *= 2) sum++;

以下代码的时间复杂度是？

01while (n > 1) n /= 2;

某算法先执行一个 O(n) 的预处理循环，再执行一个 O(n²) 的主循环，总时间复杂度是？

在含 1000 个元素的有序数组中做二分查找，最坏情况下大约需要比较多少次？

下列排序算法中，平均时间复杂度为 O(n²) 的是？

下列排序算法中，平均时间复杂度为 O(n log n) 的是？

归并排序需要开一个与原数组等长的辅助数组，其空间复杂度是？

下列排序算法中，辅助存储空间为 O(1) 的是？

用递归计算 fact(n) = n × fact(n-1)（fact(0)=1），递归深度为 n。除输入输出外，额外占用的栈空间复杂度是？

以下代码的时间复杂度是？

01for (int i = 0; i < n; i++)
02    for (int j = 0; j < n; j++)
03        for (int k = 0; k < n; k++)
04            sum++;

以下代码的执行次数是？

01for (int i = 1; i <= n; i++)
02    for (int j = 1; j <= i; j++)
03        sum++;

以下代码的时间复杂度是？

01for (int i = 1; i <= n; i++)
02    for (int j = i; j <= n; j += i)
03        sum++;

以下代码的时间复杂度是？

01for (int i = n; i >= 1; i /= 2)
02    for (int j = 0; j < n; j++)
03        sum++;

某递归算法把规模 n 的问题一分为二只保留一半继续递归（如二分查找），递归式 T(n)=T(n/2)+O(1)。它的总时间复杂度是？

某分治算法把问题分成两个规模 n/2 的子问题，合并代价 O(n)：T(n)=2T(n/2)+O(n)。总时间复杂度是？

递归式 T(n)=2T(n/2)+O(1)（分成两半但合并只花常数时间）的解是？

递归式 T(n)=T(n-1)+O(n)（每次只把规模减 1，且做 O(n) 的划分工作）的解是？

关于快速排序的时间复杂度，下列说法正确的是？

关于排序算法的「稳定性」与时间复杂度，下列说法正确的是？

用前缀和方法回答 m 次区间和查询（数组长度 n）。先 O(n) 预处理前缀和数组，之后每次查询只需 O(1)。当 m 很大时，总复杂度是？

Dijkstra 最短路有朴素实现 O(n²) 和二叉堆实现 O((n+m) log n)。关于选型，下列说法正确的是？

图为 n 个点 m 条边的有向图，用邻接表存储，对图做一次 BFS 遍历的时间复杂度是？

计算 aᵏ（k 可达 10⁹）时，采用「反复平方」的快速幂，乘法次数的量级是？

动态数组（如 C++ vector）在容量耗尽时申请两倍大小的新空间并搬迁全部元素。虽然单次 push_back 最坏要 O(n)，但从空开始连续 push n 次的平均单次代价（均摊复杂度）是？

用两个栈实现队列：入队压栈 A，出队时若栈 B 空则把 A 全部倒入 B 再弹顶。整个过程中每个元素被压入、弹出、搬运的总次数上限是？由此单次操作的均摊复杂度是？

「任何基于比较的排序算法，最坏情况时间复杂度的下界是 Ω(n log n)」。支撑这一结论的正确论述是？

关于渐进记号，下列命题正确的是？

下列关于小 o 记号（f=o(g) 表示 f/g→0）的命题中，错误的是？

递归式 T(n)=T(n/3)+T(2n/3)+cn（每次切成 1/3 与 2/3 两块，合并代价 cn）。用递归树估算，T(n) 的量级是？

以下代码的时间复杂度是？

01int i = 1, s = 0;
02while (s < n) { s += i; i++; }

以下代码中 i、j 都只增不减（cond 为某条件判断）：

01int j = 0;
02for (int i = 0; i < n; i++) {
03    while (j < n && !cond(i, j)) j++;
04    // ...使用 i, j
05}

忽略输出本身的代价，穷举 n 个元素的所有子集与穷举所有全排列，时间复杂度分别是？

朴素递归计算斐波那契 fib(n) 的时间复杂度为指数级；加入数组把每个 fib(k) 的结果缓存起来（记忆化）之后，时间与空间复杂度变为？

某评测机 1 秒约执行 10⁸ 次基本运算。对 n = 10⁵ 的输入，下列复杂度中大概率能在 1 秒内完成的是？

算法分析中，人们通常写 O(log n) 而不写底数，理由是？

完成下面的判断题和单选题。

1  #include <cstdio>
2  using namespace std;
3  int n;
4  int a[100];
5 
6  int main() {
7      scanf("%d", &n);
8      for (int i = 1; i <= n; ++i)
9          scanf("%d", &a[i]);
10      int ans = 1;
11      for (int i = 1; i <= n; ++i) {
12          if (i > 1 && a[i] < a[i - 1])
13              ans = i;
14          while (ans < n && a[i] >= a[ans + 1])
15              ++ans;
16          printf("%d\n", ans);
17      }
18      return 0;
19  }

具有 $n$ 个顶点、$e$ 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

1  #include <iostream>
2  #include <cstdlib>
3  using namespace std;
4 
5  int n;
6  int d[10000];
7 
8  int find(int L, int R, int k) {
9      int x = rand() % (R - L + 1) + L;
10      swap(d[L], d[x]);
11      int a = L + 1, b = R;
12      while (a < b) {
13          while (a < b && d[a] < d[L])
14              ++a;
15          while (a < b && d[b] >= d[L])
16              --b;
17          swap(d[a], d[b]);
18      }
19      if (d[a] < d[L])
20          ++a;
21      if (a - L == k)
22          return d[L];
23      if (a - L < k)
24          return find(a, R, k - (a - L));
25      return find(L + 1, a - 1, k);
26  }
27 
28  int main() {
29      int k;
30      cin >> n;
31      cin >> k;
32      for (int i = 0; i < n; ++i)
33          cin >> d[i];
34      cout << find(0, n - 1, k);
35      return 0;
36  }

假设输入的 $n$、$k$ 和 d[i] 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题。

以比较为基本运算，对于 $2n$ 个数，同时找到最大值和最小值，最坏情况下需要的最少比较次数为（ ）。

斐波那契数列的定义为：$F_1=1$，$F_2=1$，$F_n=F_{n-1}+F_{n-2}$（$n\ge3$）。现在用如下程序来计算斐波那契数列的第 $n$ 项，其时间复杂度为（ ）。

01F(n):
02    if n<=2 return 1
03    else return F(n-1) + F(n-2)

对于给定的 $n$，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

01int i, j, k = 0;
02for (i = 0; i < n; i++) {
03    for (j = 0; j < n; j *= 2) {
04        k = k + n / 2;
05    }
06}

以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

（容器分水）有两个容器，容器 $1$ 的容量为 $a$ 升，容器 $2$ 的容量为 $b$ 升；同时允许下列三种操作：

1. FILL(i)：用水龙头将容器 $i$（$i\in\{1,2\}$）灌满水；
2. DROP(i)：将容器 $i$ 的水倒进下水道；
3. POUR(i,j)：将容器 $i$ 的水倒进容器 $j$。完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空。

求只使用上述两个容器和三种操作，获得恰好 $c$ 升水的最少操作数和操作序列。上述 $a,b,c$ 均为不超过 $100$ 的正整数，且 $c\le\max\{a,b\}$。

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3  const int N = 110;
4 
5  int f[N][N];
6  int ans;
7  int a, b, c;
8  int init;
9 
10  int dfs(int x, int y) {
11      if (f[x][y] != init)
12          return f[x][y];
13      if (x == c || y == c)
14          return f[x][y] = 0;
15      f[x][y] = init - 1;
16      f[x][y] = min(f[x][y], dfs(a, y) + 1);
17      f[x][y] = min(f[x][y], dfs(x, b) + 1);
18      f[x][y] = min(f[x][y], dfs(0, y) + 1);
19      f[x][y] = min(f[x][y], dfs(x, 0) + 1);
20      int t = min(a - x, y);
21      f[x][y] = min(f[x][y], ①);
22      t = min(x, b - y);
23      f[x][y] = min(f[x][y], ②);
24      return f[x][y];
25  }
26 
27  void go(int x, int y) {
28      if (③)
29          return;
30      if (f[x][y] == dfs(a, y) + 1) {
31          cout << "FILL(1)" << endl;
32          go(a, y);
33      } else if (f[x][y] == dfs(x, b) + 1) {
34          cout << "FILL(2)" << endl;
35          go(x, b);
36      } else if (f[x][y] == dfs(0, y) + 1) {
37          cout << "DROP(1)" << endl;
38          go(0, y);
39      } else if (f[x][y] == dfs(x, 0) + 1) {
40          cout << "DROP(2)" << endl;
41          go(x, 0);
42      } else {
43          int t = min(a - x, y);
44          if (f[x][y] == ④) {
45              cout << "POUR(2,1)" << endl;
46              go(x + t, y - t);
47          } else {
48              t = min(x, b - y);
49              if (f[x][y] == ⑤) {
50                  cout << "POUR(1,2)" << endl;
51                  go(x - t, y + t);
52              } else
53              assert(0);
54          }
55      }
56  }
57 
58  int main() {
59      cin >> a >> b >> c;
60      ans = 1 << 30;
61      memset(f, 127, sizeof f);
62      init = **f;
63      if ((ans = dfs(0, 0)) == init - 1)
64          cout << "impossible";
65      else {
66          cout << ans << endl;
67          go(0, 0);
68      }
69  }

假设 $n$ 是图的顶点个数，$m$ 是图的边数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面四个选项中哪一项的渐近时间复杂度最小？（ ）

假设快速排序算法的输入是一个长度为 $n$ 的已排序数组，且该快速排序算法在分治过程中总是选择第一个元素作为基准元素。以下哪个选项描述的是这种情况下的快速排序行为？（ ）

现在用如下代码来计算 $x^n$，其时间复杂度为（ ）。

01double quick_power(double x, unsigned n) {
02    if (n == 0) return 1;
03    if (n == 1) return x;
04    return quick_power(x, n / 2)
05        * quick_power(x, n / 2)
06        * ((n & 1) ? x : 1);
07}

假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 $n$ 个键值对，表的装载因子为 $a$（$0 < a \le 1$）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？

递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

斐波那契数列的定义为 $F(0)=0$，$F(1)=1$，$F(n) = F(n-1) + F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的。而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？