Vérifiez si le premier grand-o

Question

Ma fonction initiale pour déterminer si un nombre est premier était:

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

Ce couru avec une complexité de O(x) que vous avez peut-être dû aller à x.

J'ai appris quelques optimisations et j'ai besoin de vérifier mon big-o. Voici le programme amélioré:

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; 
} 

Est-ce que le fait que je vais maintenant jusqu'au changement sqrt() cela O(sqrt(x))?

Answer 1

Oui, mais il n'y a pas de n s. La complexité de votre nouvelle fonction est O (sqrt (x)). Quand vous dites O (N) et ne spécifiez pas ce que N est, il est généralement pris pour être le taille de l'entrée. Ceci est déroutant pour les fonctions qui prennent un seul argument numérique, dans ce cas, vous devriez être explicite.

Answer 2

Absolument, La complexité de votre nouvelle fonction est

O (sqrt (x))

Mais encore, il y a peu de place pour l'optimisation. Jetez un oeil au code mentionné ci-dessous:

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; 
}