J'ai eu une interview aujourd'hui, on m'a demandé comment la recherche d'un numéro à l'intérieur d'un tableau, j'ai dit BinarySearch, il m'a demandé de faire preuve d'un grand tableau qui comporte des milliers de bossertions (par exemple les stocks) à la recherche d'exemple par prix de la Stocks, j'ai répété BinarySearch, il a dit que le tri de milliers de dollars prendra beaucoup de temps avant d'appliquer BinaireSearch.
Pouvez-vous s'il vous plaît supporter avec moi et m'apprendre à aborder ce problème? Merci Votre aide est appréciée.
3 Réponses :
Je ne suis pas sûr de ce qu'il avait en tête.
Si vous voulez simplement trouver le numéro une fois, et que vous n'avez aucune garantie quant à savoir si la matrice est triée, je ne pense pas que vous puissiez battre la recherche linéaire. En moyenne, vous devrez chercher à mi-chemin de la matrice avant de trouver la valeur, c'est-à-dire le temps d'exécution attendu O (n); Lorsque vous triez, vous devez toucher chaque valeur au moins une fois et probablement plus que cela, c'est-à-dire le temps d'exécution attendu O (n log n).
Mais si vous avez besoin de trouver plusieurs valeurs, le triage de temps passé rapidement. Avec une matrice triée, vous pouvez rechercher binaire dans O (journal N), donc à coup sûr de la troisième recherche que vous êtes à l'avance si vous avez investi le temps de tri.
Vous pouvez faire encore mieux si vous êtes autorisé à créer différentes structures de données pour aider au problème. Vous pouvez créer une sorte d'index, tel qu'une table de hachage; Mais la structure de données championne pour ce type de problème serait probablement une sorte de structure d'arbres. Ensuite, vous pouvez insérer de nouvelles valeurs dans l'arborescence plus rapidement que vous pouvez appendez de nouvelles valeurs et de résoudre le tableau, et la recherche va toujours être O (journalisation) pour trouver une valeur. Il existe différentes sortes d'arbres disponibles: arbre binaire, arbre B, trie, etc.
mais @ @hot Licks a dit, une table de hachage est souvent utilisée pour ce type de chose, et il est assez bon marché de mettre à jour: vous venez d'ajouter une valeur sur le tableau principal et mettez à jour la table de hachage pour pointer vers la nouvelle valeur. . Et une table de hachage est très proche de O (1) fois que vous ne pouvez pas battre. (Une table de hachage est o (1) s'il n'y a pas de collisions de hachage; supposant un bon algorithme de hachage et une table de hachage assez grande, il n'y aura presque aucune collision. Je pense que vous pourriez dire qu'une table de hachage est O (n) où n est le nombre moyen de collisions de hachage par "godet". Si je me trompe, je m'attends à être corrigé très rapidement; c'est Stackoverflow!)
Je n'ai pas compris qu'est-ce que tu voulais dire par troisième recherche? toute exférence plz?
Si vous devez rechercher une seule fois, puis vous avez terminé, la recherche linéaire est la plus rapide. Si vous devez rechercher deux fois, la recherche linéaire peut toujours être plus rapide que le tri et la recherche binaire; En moyenne, la recherche linéaire devra passer environ la moitié des valeurs, de sorte que deux recherches linéaires devraient en moyenne besoin de passer par toutes les valeurs. Si vous devez rechercher trois fois, trier une fois, à l'aide de la recherche binaire des trois recherches doit être la plus rapide. Si vous devez rechercher quatre fois ou plus, il est identique à trois fois: trier d'abord alors faire une recherche binaire.
Si vous devez effectuer une recherche plus de deux fois, vous ferez probablement mieux d'utiliser la table de hachage.
Je pense que l'intervieweur veut que vous analysiez dans différents cas sur l'état initial de la matrice, quel algorithme utiliserez-vous. De cause, vous devez savoir que vous pouvez construire une table de hachage puis O (1) peut trouver le numéro ou lorsque le tableau est trié (temps passé sur le tri peut être utilisé), vous pouvez utiliser BinarysSearch ou utiliser d'autres structures de données pour terminer le travail.
Alors enfin, je veux dire qu'il n'y a pas de réponse correcte pour cette question.
On m'a posé une question similaire.La torsion était de rechercher dans le tri et ensuite un tableau non formé. Ces réponses étaient toutes les réponses non acceptées
À la fin, j'ai reçu un retour négatif. Bien que nous pensions que l'une des réponses ci-dessus est une solution, mais il y a sûrement quelque chose de spécial dans la recherche linéaire qui me manque.
à noter le tri avant la recherche est également une surcharge sur le plan de la recherche, surtout si vous utilisez des structures de données supplémentaires entre les deux.
Tous les commentaires sont accueillis.
Je dirais pour un arbre binaire trié et désormais désormais possible, vous pouvez trier comme votre 1) réponse. L'autre sens serait de se déplacer sur la matrice et de sauvegarder les données dans la table de hachage O (n) et recherchez les données sur la table de hachage serait O (1). Mais la recherche devrait être dans la boucle. Si les données existent, vous n'avez pas besoin de l'enregistrer. Qu'en penses-tu?
Généralement, pour rechercher un grand ensemble de choses, on utilise une sorte de table de hachage.
qui est plus rapide, recherche de hasch ou recherche binaire?
@Josh - Question touristique. La recherche binaire est plus rapide si tout est bien trié et que vous ne modifiez jamais l'ensemble pour être recherché. Mais ce n'est pas une vraie vie. Dans la vie réelle, la table de hachage gagne presque toujours.