J'ai récemment entendu parler de recherche ternaire dans laquelle nous divisons un tableau en 3 parties et comparons. Ici, il y aura deux comparaisons mais cela réduira le tableau à n / 3. Pourquoi les gens ne l'utilisent-ils pas autant?
Réponses
Trop de publicités?
En fait, les gens utilisent des arbres k-ary pour k arbitraires.
C'est cependant un compromis.
Pour trouver un élément dans un arbre k-aire, vous avez besoin d'environ k * ln (N) / ln (k) opérations (rappelez-vous la formule de changement de base). Plus votre k est grand, plus vous avez besoin d'opérations globales.
L'extension logique de ce que vous dites est "pourquoi les gens n'utilisent-ils pas un arbre N-aire pour N éléments de données?". Ce qui, bien sûr, serait un tableau.
Akusete
Points
4597
Michael Burr
Points
181287
Rechercher 1 milliard (1 milliard - 1 milliard de dollars US) d'éléments triés prendrait en moyenne environ 15 comparés à la recherche binaire et environ 9 comparés à une recherche ternaire - ce qui n'est pas un avantage énorme. Et notez que chaque "comparaison ternaire" peut impliquer 2 comparaisons réelles.
supercat
Points
25534
La seule façon d'un ternaire de recherche peut être plus rapide qu'une recherche binaire est si un 3-way partition détermination peut être fait pour moins de 1.55 fois le coût d'un 2-way comparaison. Si les articles sont stockés dans un tableau trié, le 3-way de la détermination en moyenne à une valeur de 1,66 fois plus cher que le 2 sorte de détermination. Si les informations sont stockées dans un arbre, cependant, le coût d'extraction de l'information est relativement élevé par rapport au coût de comparer, et de la localité de cache signifie que le coût de hasard récupérer une paire de données n'est pas bien pire que le coût de récupérer une donnée, un ternaire ou n-chemin de l'arbre peut améliorer grandement l'efficacité.
