J'ai codé un algorithme de recherche dans un tableau trié avec complexité log2 (n)/5 .Est-ce utile?Existe-t-il un algorithme pour rechercher un élément dans un tableau trié avec une complexité inférieure à log2 (n)
Il est prouvable que vous ne pouvez pas obtenir plus bas que O (log (n)) pour une recherche qui suppose seulement des opérations de comparaison. une complexité de log2 (n)/5 est la même chose que O (log (n)).
L'utilité dépend de ce que vous l'utilisez.
Il n'est pas possible de faire mieux que log₂n sans aucune autre supposition sur le tableau autre que le tri, ou sans aucune précomputation/création de structure de données.
Comment proposez-vous de terminer en étapes de moins de log₂n si l'élément que vous recherchez ne se trouve pas dans votre tableau?
cet algorithme fonctionne pour la liste des nombres aléatoires. J'ai donné des données de test de 5,20,000 nombres aléatoires. Donc je pense qu'il peut être utile dans chaque problème et parfois dans le cas de petits nombres sa complexité est juste proche de la complexité constante. dans le cas où le numéro n'est pas présent, la complexité est meilleure oflog2n –
Dans ce cas, il existe des algorithmes O (loglogn). Voir: http://www.dcc.uchile.cl/~rbaeza/ftp/tour.ps.gz – Imran
Bien sûr, vous pouvez toujours discuter si oui ou non une recherche non linéaire est nécessairement plus rapide qu'une recherche linéaire: http://www.ddj.com/184405848
Ie, si vous êtes à la recherche d'une ligne de cache, il peut être plus rapide pour le fouiller linéairement que ramification.
Hm. Question difficile. Pourquoi ne publiez-vous pas votre algorithme et laissez-nous voir ce que vous faites. Cependant, pour une victoire réelle, vous devriez être meilleur que O (log2 log2 (n))? C'est ce que la recherche d'interpolation fait en moyenne ..
monsieur, je pense qu'il est juste proche de log2 (log2 (n)). Mais je ne peux pas le prouver mathematically.i l'ont fait sur les données aléatoires de la taille comme (10,100,1000,10000 jusqu'à 512000) .et mo des opérations sont log2() de l'opération no dans binary.it est basé sur l'hypothèse que les nombres sont sur l'écart constant comme (5, 10,15,20,25) –
bien que j'avais posé cette question pour voir si mon algo est nouveau ou pas. Et de ton aide j'ai trouvé que c'est juste une recherche d'interpolation. –
Je pense qu'il serait utile que si elle est plus rapide que d'autres algorithmes de recherche de O (logn) existants dans la pratique. En d'autres termes, si vos tests de performances montrent des améliorations de vitesse. Cependant, pour de très grandes entrées, les améliorations de temps constantes (comme 1/5) ne font pas beaucoup de différence. C'est pourquoi la plus grande importance est donnée à la complexité asymptotique d'un algorithme.
cet algorithme fonctionne pour la liste des nombres aléatoires .j'ai donné des données de test de 5,20,000 nombres aléatoires .Si je pense qu'il peut être utile dans tous les problèmes et parfois dans le cas de petits nombres sa complexité est juste proche de constante complexité. –
vous semblez avoir une légère idée fausse sur ce qu'est exactement la complexité. – shoosh