Exercice en Algorithme et Complexité

Question

Bonjour 
j'ai un exercice en algorithme et complexité et j'ai pas pu le resoudre et j'espere que vous pouvez m'aider 
l'exercice est le suivant: 
Donner un algorithme recursif qui determine si tous les elements d'un tableau de taille n sont distincts et calculer la complexité de cet algorithme 


c'est urgent svp svp svp si quelqu'un peut m'aider n'hesitez pas de m'aider

gnairod · Answer

Bonjour,

Il faut determiner si le tableau est deja trie lorsque tu le recois ou si ce n'est pas le cas.

Dans le cas ou il est deja trie la complexite est lineaire, sinon quadratique ou bien tu fais tri + comparaison soit nln(n)/ln(2) + n.

Au revoir,

nostalgieing · Answer

Bonjour
merci j'ai fais un algorithme recursif qui permet de determiner si les elements d'un tableau sont distinct et il est ci dessous et j'espere que tu le vois et me dis est ce que il est acceptable ou non mais j'ai pas pu calculer sa comlexité c'est pourquoi si vous pouvez aidez-moi dans le calcul de la complexité de mon algorithme
int i,j 
boolean tousDistincts=true 

for(i de 1 à n) 
fonction tester(int i, int j) 
if(T[i]==T[j]) 
tousDistincts==false 
else 
tester(i,j+1) 
end 
endfunction 
end

nostalgieing · Answer

bonjour 
Desolée pour le derangement  mais j'ai une autre probleme et j'espere que vous pouvez 'aider c'est urgent

j'ai une ambiguté en algorithme et complexité et j'ai quelques questions à poser et j'ai besoin de vos aide c'est urgent 
1-quelle est la methode parmis tri par selection tri par insertion et tri par comptage la plus rapide lorsqu'elle s'applique sur un tableau trié 
2-est ce que le nombre d'opération effectuées par la procedure tri fusion pour trier un tableau depend des valeurs de ce tableau 
3-combien d'operation on effectue si on tri un tableau de taille N avec la procedure Tri rapide

pleeeeeeeeeeeeeeeeease j'ai besoin de l'aide pour depasser ces ambiguité

gnairod · Answer

1) Depend de l'implementation du tri par insertion mais si elle est bonne alors tri par insertion.

En effet tri par selection toujours O(n^2) comparaisons, tri par insertion O(n) et tri par comptage O(n) mais du fait du comptage est de l'allocation memoire O(nk) donc gagne le tri par insertion.

2) Absolument pas, cela ne depend que de la taille.

3) Cela depend du cas dans lequel tu te trouves. O(n^2) si pire des cas et O(n*log2(n)) dans le cas moyen (a la constante multiplication pres) et dans le meilleur.

Exercice en Algorithme et Complexité

4 réponses

Votre réponse

Discussions similaires