Проверьте, если премьер биг-о

Question

Проверьте, если премьер биг-о

Моя оригинальная функция, чтобы определить, было ли число простым:

bool is_prime(int x) {
for (int y = 2; y < x; ++y) {
if (x % y == 0) {
return false;
}
}
return true;
}

Это побежал со сложностью O(x) как вы могли бы пойти в x,

Я узнал о некоторых оптимизациях и нуждаюсь в проверке моего биг-о. Вот улучшенная программа:

bool is_prime(int x)
{
if (x % 2  == 0 && x > 2) {
return false;
}
for (int y = 3; y*y <= x; y += 2) {
if (x % y == 0) {
return false;
}
}
return true;
}

Имеет ли тот факт, что я сейчас иду к sqrt() изменить это на O(sqrt(x))?

6

asymptotic-complexity big-o c++

Решение

Другие решения

Абсолютно,
Сложность вашей новой функции

O (SQRT (х))

Но все же есть место для оптимизации. Посмотрите на код, указанный ниже:

bool isPrime(int n)
{
// Boundary cases
if (n <= 1)  return false;
if (n <= 3)  return true;

// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;

for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;

return true;
}

1

Источник

Accepted Answer

Да, но здесь нет ns. Сложность вашей новой функции O (SQRT (х)). Когда ты сказал НА) и не уточняйте что N это, как правило, считается размер ввода. Это сбивает с толку для функций, которые принимают один числовой аргумент, поэтому в этих случаях вы должны быть явными.

7