Méthode temps/espace-complexité

Question

J'ai une question à laquelle je peux répondre avec la meilleure complexité possible.

Nous avons obtenu un tableau trié (int) et une valeur X. Tout ce que nous devons faire est de trouver combien d'endroits dans le tableau est égal à la valeur X.

Ceci est ma solution à cette situation, car je ne connais pas grand-chose à la complexité. que je sais est que de meilleures méthodes sont sans pour les boucles: X

class Question 
{ 
    public static int mount (int [] a, int x) 
    { 
     int first=0, last=a.length-1, count=0, pointer=0; 
     boolean found=false, finish=false; 
     if (x < a[0] || x > a[a.length-1]) 
       return 0; 
     while (! found) **//Searching any place in the array that equals to x value;** 
     { 
      if (a[(first+last)/2] > x) 
       last = (first+last)/2; 
      else if (a[(first+last)/2] < x) 
       first = (first+last)/2; 
      else 
      { 
       pointer = (first+last)/2; 
       count = 1; 
       found = true; break; 
      } 
      if (Math.abs(last-first) == 1) 
      { 
       if (a[first] == x) 
       { 
        pointer = first; 
        count = 1; 
        found = true; 
       } 
       else if (a[last] == x) 
       { 
        pointer = last; 
        count = 1; 
        found = true; 
       } 
       else 
        return 0; 
      } 
      if (first == last) 
      { 
       if (a[first] == x) 
       { 
        pointer = first; 
        count = 1; 
        found = true; 
       } 
       else 
        return 0; 
      } 
     } 
     int backPointer=pointer, forwardPointer=pointer; 
     boolean stop1=false, stop2= false; 
     while (!finish) **//Counting the number of places the X value is near our pointer.** 
     { 
      if (backPointer-1 >= 0) 
       if (a[backPointer-1] == x) 
       { 
        count++; 
        backPointer--; 
       } 
       else 
        stop1 = true; 
      if (forwardPointer+1 <= a.length-1) 
       if (a[forwardPointer+1] == x) 
       { 
        count++; 
        forwardPointer++; 
       } 
       else 
        stop2 = true; 
      if (stop1 && stop2) 
       finish=true; 
     } 
     return count; 
    } 
    public static void main (String [] args) 
    { 
     int [] a = {-25,0,5,11,11,99}; 
     System.out.println(mount(a, 11)); 
    } 
} 

Le comte commande Réussissez vos impressions et copies « 2 ».

Je veux juste savoir si quelqu'un peut penser à une meilleure complexité pour cette méthode.

En outre, comment puis-je savoir quelle est la complexité temps/espace de la méthode? Tout ce que je sais sur la complexité temps/espace est que pour la boucle est O (n). Je ne sais pas comment calculer la complexité de ma méthode.

Merci beaucoup!

Montage: Ceci est la seconde boucle while après le changement:

 while (!stop1 || !stop2) //Counting the number of places the X value is near our pointer. 
    { 
     if (!stop1) 
     { 
      if (a[last] == x) 
      { 
       stop1 = true; 
       count += (last-pointer); 
      } 
      else if (a[(last+forwardPointer)/2] == x) 
      { 
       if (last-forwardPointer == 1) 
       { 
        stop1 = true; 
        count += (forwardPointer-pointer); 
       } 
       else 
        forwardPointer = (last + forwardPointer)/2; 
      } 
      else 
       last = ((last + forwardPointer)/2) - 1; 
     } 
     if (!stop2) 
     { 
      if (a[first] == x) 
      { 
       stop2 = true; 
       count += (pointer - first); 
      } 
      else if (a[(first+backPointer)/2] == x) 
      { 
       if (backPointer - first == 1) 
       { 
        stop2 = true; 
        count += (pointer-backPointer); 
       } 
       else 
        backPointer = (first + backPointer)/2; 
      } 
      else 
       first = ((first + backPointer)/2) + 1; 
     } 
    } 

Que pensez-vous du changement? Je pense que cela changerait la complexité temporelle en O (long (n)).

Answer 1

Examinons d'abord votre code:

Le code pourrait être fortement remanié et nettoyé (ce qui entraînerait également la mise en œuvre plus efficace, mais sans améliorer le temps ou la complexité de l'espace), mais l'algorithme lui-même est assez bon . Ce qu'il fait est d'utiliser la recherche binaire standard pour trouver un élément avec la valeur requise, puis balaie vers l'arrière et vers l'avant pour trouver toutes les autres occurrences de la valeur.

En termes de complexité temporelle, l'algorithme est O (N). Le pire des cas est lorsque le tableau entier a la même valeur et que vous finissez par l'itérer tout au long de la 2ème phase (la recherche binaire ne prendra qu'une seule itération). La complexité spatiale est O (1). L'utilisation de la mémoire (espace) n'est pas affectée par la croissance de la taille d'entrée.

Vous pouvez améliorer la complexité du pire cas si vous continuez à utiliser la recherche binaire sur les deux sous-matrices (retour & avant) et augmenter logarithmiquement la "plage de correspondance". La complexité temporelle devient O (log (N)). La complexité de l'espace restera O (1) pour la même raison que précédemment. Cependant, la complexité moyenne pour un scénario réel (où le tableau contient diverses valeurs) serait très proche et pourrait même pencher vers votre propre version.