Forum Prepas.org

Salut ! J'aimerais savoir s'il y'a un moyen optimisé ( c-a-d meilleur que l'algo naïf en O(n²)) pour tester l'absence de répétition d'une valeur dans un tableau en Caml.
Je me doute bien que ça existe, mais je sature et j'arrive pas à trouver (ou à expliquer pourquoi il n'en existerait pas). Merci de votre aide.

Si tu peux utiliser une structure de données auxiliaire avec insertion et recherche en O(f(n)), alors tu as un algorithme en O(n f(n)).

Exemple si tu peux hasher tes données: table de hashage, insertion et recherche en O(1), tu as un algorithme en O(n), et c’est évidemment optimal.

Exemple si tu peux trier tes données: arbre binaire rouge-noir, insertion et recherche en O(log n), tu as un algorithme en O(n log n).

Si les éléments sont des entiers et sont bornées on a un algorithme en O(N) sans table de hachage, en utilisant une stratégie similaire au counting sort.

Merci de vos réponses.
Je vois que les algos pour y parvenir ne sont pas triviaux, donc j'imagine que l'épreuve attendait un algo naïf en O(n²).

Comment parvenir en O(n) pour trier ET rechercher un élément sur un tableau Errys ? Ou alors tu voulais dire O(nlogn) ?

EDIT : Ah j'ai compris N doit être la borne ?

il y a un petit gag ici.
Si on suppose disons qu'on est sur R alors on n'a pas mieux que n log n.
Mais mais mais "Si les éléments sont des entiers et sont bornées" : informatiquement ça n'a pas trop de sens Tous les nombres machines sont bornés (sauf inf et NaN en IEEE754 mais bon...) et "entier" ne veut rien dire non plus. Si j'ai disons 64bits, ça représente peut etre un flotant mais je peux aussi le voir comme un brave entier 64bits. bref, tout ça pour dire que l'informatique *machine*, ça se passe toujours sur une partie bornée de N.
Je dis *machine* car on peut aussi avoir des nombres en representation "infinie" (la bonne blague en réalité) mais dans ce cas un nombre est une liste et il faut un algo et non une seule et unique instruction CPU pour faire + ou *.

autre partie du fun : la complexité en temps c'est bien mais :
1) c'est souvent un O donc on a des algo "meilleurs" mais dont les constantes sont horribles et donc en pratique on prend parfois du n² au lieu de n log n avec une constant horrible (si on sait qu'on restera sur des petits jeux de données).
2) il faut regarder la complexité mémoire. Si on autant de mémoire qu'on veut, certains algo deviennent triviaux.

fakbill a écrit : ↑

01 déc. 2017 10:55

bref, tout ça pour dire que l'informatique *machine*, ça se passe toujours sur une partie bornée de N.

Plutôt dans Z/nZ. (Avec n souvent puissance de 2.)

Je pensais plutôt au cas où l'on avait un tableau de chaine de caractère par exemple, ou un objet quelconque qui ne peut pas être représenté par un simple entier sans perdre d'informations.

Mais sinon c'est vrai que ça devient intéressant dans R, comment ferais tu une stratégie similaire au counting sort avec des flottante ? Je ne vois pas trop de manière de convertir un flottant en entier (pour l'utiliser comme index) à moins de multiplier par 10^(precision) et donc avoir besoin de beaucoup trop d'espaces...

Desert a écrit : ↑

01 déc. 2017 09:52

Merci de vos réponses.
Je vois que les algos pour y parvenir ne sont pas triviaux, donc j'imagine que l'épreuve attendait un algo naïf en O(n²).

Comment parvenir en O(n) pour trier ET rechercher un élément sur un tableau Errys ? Ou alors tu voulais dire O(nlogn) ?

EDIT : Ah j'ai compris N doit être la borne ?

Si tes entiers étaient compris entre 0 et 100 tu aurais un tableau de booleen indexé de 0 à 100 initialisé à false.
Tu parcours ta liste et pour chaque élément tu regardes si tu l'as déjà vu, si c'est le cas, c'est qu'il y a un élément en double. D'où le O(N) (N étant le nombre d'éléments)

"Si tes entiers étaient compris entre 0 et 100 tu aurais un tableau de booleen indexé de 0 à 100 initialisé à false.
Tu parcours ta liste et pour chaque élément tu regardes si tu l'as déjà vu, si c'est le cas, c'est qu'il y a un élément en double. D'où le O(N) (N étant le nombre d'éléments)"

Merci ! J'ai compris

Errys a écrit : ↑

01 déc. 2017 08:48

Si les éléments sont des entiers et sont bornées on a un algorithme en O(N) sans table de hachage, en utilisant une stratégie similaire au counting sort.

Ça n’est rien d’autre qu’une table de hashage, avec une fonction de hash très simple: l’identité.

siro : si tu veux. c'était juste pour dire "PAS sur R ni même sur une partie de R". On a N bits, donc on peut représenter 2^N machins qu'on appelle des nombres car les operations standards ressemblent à celle sur N ou sur R...mais elle ne font que ressembler.

Sinon oui, les buckets et le hachage c'est puissant et souvent oublié/mal compris.