GESP 8级客观题｜高阶复杂度与算法优化｜课堂讲解

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

1. 有 V 个顶点、 E 条边的图的深度优先搜索遍历时间复杂度为

   {{ select(1) }}

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

2. 下⾯程序的时间复杂度为

  bool notPrime[N] = {false};
  void sieve() {
  	for (int n = 2; n * n < N; n++)
  		if (!notPrime[n])
  			for (int i = n * n; i < N; i += n)
  				notPrime[i] = true;
  }

{{ select(2) }}

• $O(N)$
• $O(N x log N)$
• $O(N x log log N)$
• $O(N^{2})$