GESP 5级客观题｜算法复杂度分析｜课堂讲解

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

1. 下面代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 $N$ 是否素数，有关其时间复杂度的正确说法是（ ）

#include<iostream>
#include<cmath>
using namespace std;
bool isPrimeA(int N){
	if(N < 2)
		return false;
	for(int i = 2; i < N; i++)
		if(N % i == 0)
			return false;
	return true;
}
bool isPrimeB(int N){
	if(N < 2)
		return false;
	int endNum = int(sqrt(N));
	for(int i = 2; i <= endNum; i++)
		if(N % i == 0)
			return false;
	return true;
}
int main(){
	cout << boolalpha;
	cout << isPrimeA(13) << " " << isPrimeB(13) << endl;
	return 0;
}

{{ select(1) }}

• isPrimeA() 的最坏时间复杂度是$O(N)$ ， isPrimeB() 的最坏时间复杂度是 $O(\log N)$ ， isPrimeB() 优于isPrimeA()。
• isPrimeA() 的最坏时间复杂度是$O(N)$ ， isPrimeB() 的最坏时间复杂度是 $O(N^{\frac{1}{2}})$ ， isPrimeB() 优于isPrimeA()。
• isPrimeA() 的最坏时间复杂度是$O(N^{\frac{1}{2}})$ ， isPrimeB() 的最坏时间复杂度是 $O(N)$ ， isPrimeA() 优于isPrimeB()。
• isPrimeA() 的最坏时间复杂度是$O(\log N)$ ，isPrimeB() 的最坏时间复杂度是 $O(N)$ ， isPrimeA() 优于isPrimeB()。

2. 下⾯函数可以将 n 的所有质因数找出来，其时间复杂度是（ ）。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
    vector<int> factors;

    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }

    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }

    if (n > 2) {
        factors.push_back(n);
    }

    return factors;
}

{{ select(2) }}

• $O(n^2)$
• $O(n log n)$
• $O(\sqrt{n} log n)$
• $O(n)$