Algorithme de recherche dichotomique
maya80
Messages postés
52
Date d'inscription
Statut
Membre
Dernière intervention
-
maya80 Messages postés 52 Date d'inscription Statut Membre Dernière intervention -
maya80 Messages postés 52 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Voilà, j'ai ce problème qui est très urgent:
Étant donné un tableau trié t de n nombres entiers, on veut appliquer la recherche dichotomique, supposons que le tableau t contient m éléments, dont presque tous sont égaux à l'infini (disons le plus grand entier pouvant être stocké dans un mot de mémoire). Plus précisément, supposons que les valeurs finies (< infini) sont stockées aux indices compris entre 1 et n et que n est beaucoup plus petit que m. Dans un tel tableau, la fouille dichotomique prend un temps proportionnel à logm. Décrivez un algorithme de recherche dichotomique qui détermine, en un temps dans O(log n) (et non O(logm)), si un nombre x < infini apparaît dans t ou non.
Ce que je veux savoir, c'est comment ecrire un algorithme qui soit de complexité logn alors que la taille du tableau est m.
Merci à tout le monde.
Voilà, j'ai ce problème qui est très urgent:
Étant donné un tableau trié t de n nombres entiers, on veut appliquer la recherche dichotomique, supposons que le tableau t contient m éléments, dont presque tous sont égaux à l'infini (disons le plus grand entier pouvant être stocké dans un mot de mémoire). Plus précisément, supposons que les valeurs finies (< infini) sont stockées aux indices compris entre 1 et n et que n est beaucoup plus petit que m. Dans un tel tableau, la fouille dichotomique prend un temps proportionnel à logm. Décrivez un algorithme de recherche dichotomique qui détermine, en un temps dans O(log n) (et non O(logm)), si un nombre x < infini apparaît dans t ou non.
Ce que je veux savoir, c'est comment ecrire un algorithme qui soit de complexité logn alors que la taille du tableau est m.
Merci à tout le monde.
A voir également:
- Algorithme de recherche dichotomique
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Rechercher ou entrer l'adresse mm - recherche google - Guide
- Recherche photo - Guide
- Je recherche une chanson - Guide
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
2 réponses
bonjour
si j'ai bien compris ton énonce tu as un tableau couper en 2 parties
la premiere de 1 à n avec les valeur < infini
la deuxieme de n a m avec les valeur "> infini"
je me plante peut etre mais ca me parait simple il te suffit de faire une recherche dichotomique en allant de 1 à n .....
non ?
Adns
si j'ai bien compris ton énonce tu as un tableau couper en 2 parties
la premiere de 1 à n avec les valeur < infini
la deuxieme de n a m avec les valeur "> infini"
je me plante peut etre mais ca me parait simple il te suffit de faire une recherche dichotomique en allant de 1 à n .....
non ?
Adns