Recherche optimisée - quelqu'un peut-il aider à calculer la complexité de cet algorithme

Question

lorsque j'ai regardé l'algorithme de recherche binaire. J'ai le sentiment que le point de recherche pourrait être optimisé en ne regardant pas toujours le point central. Par exemple, si nous recherchons un mot dans le dictionnaire sans regarder le menu, nous ne nous tournerons pas toujours vers la page du milieu pour comparer. Si le mot commence par 'A', nous l'attendrons au début. Si cela commence par 'Z', nous essaierons certainement avec les pages à la fin. Mais, en utilisant toujours la densité de la matrice cible actuelle, il y aura un problème important si la densité de la matrice change radicalement, ce qui entraînera dans certains cas une complexité proche de O (n). Ainsi j'ai calculé la densité basée sur la recherche précédente, et calcule toujours la densité de la plus petite division. Et calcule le point de recherche toujours à partir du point de recherche précédent. En cela, il atténue l'impact de la densité changeante. Par conséquent, j'ai écrit ce code en essayant de générer une recherche optimisée.

Je ne l'ai pas testé (même pas encore compilé). Mais je suppose que cela explique l'algorithme:

public int OptimizedSearch(int a[], int target) { 
     return OptimizedSearch(a, target, 0, a.size(), 0, true); 
    } 

    public int OptimizedSearch(int a[], int target, int start, int end, double density, boolean fromStart) { 
     // Since density is different from the density in current target array, the search point calculated from density will 
     // always start from last search point. fromStart records whether the last search point happens at start or end of 
     // current array 
     if (0 == density) { //Initial density 
      density = (a[end] - a[start])/(end - start); 
     } 

     int searchPoint;  
     if (fromStart) { 
      searchPoint = start + ((target - a[start])/density).intValue(); 
     } 
     else { 
      searchPoint = end - ((a[end] - target)/density).intValue(); 
     } 

     if (a[searchPoint] == target) { 
      return searchPoint; 
     } 
     else if (target < a[searchPoint]) { 
      double currentDensity; 
      if (end - searchPoint > searchPoint - start) { 
       currentDensity = (a[searchPoint] - a[start])/(searchPoint - start); 
      } 
      else { 
       currentDensity = (a[end] - a[searchPoint])/(end - searchPoint); 
      } //Density is always calculated from the smaller part since it will be more accurate. 
      return OptimizedSearch(a, target, start, searchPoint - 1, currentDensity, false); 
     } 
     else { 
      double currentDensity; 
      if (end - searchPoint > searchPoint - start) { 
       currentDensity = (a[searchPoint] - a[start])/(searchPoint - start); 
      } 
      else { 
       currentDensity = (a[end] - a[searchPoint])/(end - searchPoint); 
      } //Density is always calculated from the smaller part since it will be more accurate. 
      return OptimizedSearch(a, target, searchPoint + 1, end, currentDensity, true); 
     } 
    } 

Mais j'ai vraiment du mal à calculer la complexité. J'ai le sentiment qu'il devrait être plus bas que log (N), mais je ne peux pas le prouver. Quelqu'un peut-il aider avec?

Answer 1

Ceci est une implémentation de interpolation search et si l'approximation de la distribution des éléments est assez bonne, elle a un log de complexité (log (n)). Il est loin d'être trivial de le prouver, cependant.