g5-04181. GESP-5级-2023-12-单选-第08题 未做

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

bool isPrimeA(int N)
{
    if (N < 2)
        return false;
    for (int i = 2; i <= N / 2; i++)
        if (N % i == 0)
            return false;
    return true;
}
bool isPrimeB(int N)
{
    if (N < 2)
        return false;
    for (int i = 2; i <= sqrt(N); i++)
        if (N % i == 0)
            return false;
    return true;
}

• A. isPrimeA() 的最坏时间复杂度是 $O(\frac{N}{2})$，isPrimeB() 的最坏时间复杂度是 $O(\log N)$，isPrimeA() 优于 isPrimeB()
• B. isPrimeA() 的最坏时间复杂度是 $O(\frac{N}{2})$，isPrimeB() 的最坏时间复杂度是 $O(N^{\frac{1}{2}})$，isPrimeB() 绝大多数情况下优于 isPrimeA()
• C. isPrimeA() 的最坏时间复杂度是 $O(N^{\frac{1}{2}})$，isPrimeB() 的最坏时间复杂度是 $O(N)$，isPrimeA() 优于 isPrimeB()
• D. isPrimeA() 的最坏时间复杂度是 $O(\log N)$，isPrimeB() 的最坏时间复杂度是 $O(N)$，isPrimeA() 优于 isPrimeB()