Mémoire Hydradation

Bonjour, je viens de finir ma fonction pour l'exercice Hydratation du QCM.
Elle a passée les test de vérification mais pas ceux de performance (test07).
Ce que je ne comprend pas c'est que j'ai simplifié au maximum ma fonction, mais j'ai toujours l'erreur.
Est-il possible que cette erreur viennent de l'utilisation d'un set qui provoque cela.

Merci

Oh oui!

C'est ton algorithme qui provoque cela.
En C++, std::set est souvent un arbre et std::unordered_set une table de hachage.
Il faut que tu prenne en compte la complexité des fonctions de la librairie standard du langage que tu utilises (O(log n) pour les opérations de bases sur std::set). Bien sur, même en utilisant une structure de donnée plus adaptée, tu peux ne pas passer les tests de performance (si il faut, un arbre est utilisé dans l'algo optimal), mais c'est déjà un bon début.

Hmmm ... Pour autant que j'en sache, un arbre est inutile pour hydratation.

Rooo mais chut, laissez les chercher un peu.

Ok merci pour vos réponses qui vont me donner un peu de boulot xD car ce sont des notions que je n'ai pas encore étudier (O(log N).
Et il faut donc que je trouve une autre méthode qu'un arbre pour répondre a ce défis, je vais chercher, merci.

Euh... De toute façon, comme l'a dit Equinoxe : "Un arbre est inutile". Donc la complexité O(ln N) ne te sert à rien (enfin... à priori. Je n'ai pas trouvé l'algo de ce problème, donc je ne sais pas à quoi il ressemble).

Pour le cas, la complexité est bien en O(ln N), mais elle ne vient pas d'un arbre ! =p

En elevant l'arbre et en passant pas un itérateur, j'y suis finalement arrivé, mais j'en suis maintenant au test n°9 sur le limite de temps.
Le degrès de complexité servent a décrire un temps de résolution et de calcul de l'algorithme si j'ai bien compris, un peu comme une 'mesure universelle' non ?

Merci.

Plutôt donner une approximation: Si t'as un code qui fait 1000n opérations, il sera de complexité O(n), et un code qui fait 3n² opérations sera de complexité O(n²). Mais pour n petit, le premier code sera plus lent que le second.

Ce qu'on peut dire c'est que pour n-> infini, O(ln n) plus rapide que O(n)

En général on rencontre souvent des complexités :
- constantes : O(1)
- logarithmiques : O(log N)
- linéaires : O(N)
- quadratiques : O(N\^k)
- exponentielles : O(k\^N)

Le reste étant des combinaisons de ces complexités, comme O(N*log N).

O(N!) n'est pas un ordre de grandeur à part entière, en effet selon la formule de Stirling http://fr.m.wikipedia.org/wiki/Formule_de_Stirling au voisinage de l'infini factorielle se comporte comme O(log N * N\^N).

(si je dis des trucs faux, hésitez pas :P)

@serialk: "quadratiques : O(N\^k)"... polynomiale.

Pardon, O(N\^k) c'est polynomiale et O(n²) c'est un quadratique (mais donc polynomial)

Pour les détails : http://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes#Complexit.C3.A9.2C_comparatif

D'ailleurs on peut prendre n'importe quelle fonction f() et dire qu'elle est de la complexité O(f(n)) (mais si c'est pour la comparer avec des fonctions sans f() dedans c'est débile).