GESP 8级客观题｜高阶复杂度与算法优化｜课后作业

考试频率：高频。本卷共 6 题。

1. 下⾯程序的最差时间复杂度为

int gcd(int m, int n) {
	if (m == 0)
		return n;
	return gcd(n % m, m);
}

{{ select(1) }}

• $O(根号n)$
• $O(log(n))$
• $O(n)$
• $O(1)$

2. 在⼀个包含 v 个顶点、 e 条边的带权连通简单有向图上使⽤Dijkstra算法求最短路径， 时间复杂度为$O(v^{2})$，可进⼀步优化⾄O(e+vlog(v))

   {{ select(2) }}

• 正确
• 错误

3. 在N个元素的⼆叉排序树中查找⼀个元素， 最差情况的时间复杂度是O(logN)

   {{ select(3) }}

• 正确
• 错误

4. 假设图 graph 中顶点数 v、边数 e，Dijkstra 算法的时间复杂度为？

   {{ select(4) }}

• O(V^2)
• O(E + V log V)
• O(E log V)
• O(E + V)

5. 快速排序算法的平均时间复杂度是多少？

   {{ select(5) }}

• O(N log N)
• O(N^2)
• O(N)
• O(log N)

6. 对 N 个元素的数组进行排序，快速排序和归并排序的平均时间复杂度都为 $O(N log N)$，但快速排序存在退化情况，使得时间复杂度升高至 $O(N^2)$；归并排序需要额外的空间开销。

   {{ select(6) }}

• 正确
• 错误