Bonjour à tous,
Dans le cadre de mon cours, le prof nous a donnée un petite exercices ou on doit trouver la médiane dans un tableau de X élements, ou certains éléments peuvent se répéter.
Normalement, ça serait facile de le trouver je commencerais par trier mon tableau et je retourne élément N/2 (tableau impair) ou encore la moyenne de N/2 & N/2+1 (tableau impair). Cependant, le prof nous donne une contrainte qui me fait bloquer entièrement, il refuse qu'on tri le tableau.
En gros, mon algorithme doit :
- Calculer et retourner la médiane d'un tableau sans le trier.
- Déterminer la moyenne du tableau
- Déterminer le nombre d’élément plus petit que la moyenne.
Ensuite je vais devoir déterminer :
- Temps d’exécution dans le pire cas
- Temps d'exécution dans le meilleur cas.
En cherchant sur internet, je suis tombé sur certaine site ou on parlais de calcul linéaire,déterminisme,etc. Mais j'ai rien trouvé qui me donnée une explication claire si je peu le dire ainsi. Surtout que dans la plus part des cas, les données du tableau était permuter.
En faisant quelques tests j'ai sortis 5,6 version d'Algo différent que j'ai tester en le transposant en C#, cependant je me retrouver toujours que dans certains cas de tests j'ai une erreur.
Merci d'avance !
Partager