Salut,jaurai quelques question en fait,si les proposition sont vrai ou pas:
 
1/La recherche dun element dans un tableau trié ou non trié a la meme complexite dans les 2 cas?
 
2/Pkoi dans un tableau dentier trié ,la plus grande difference
en valeur absolue entre 2 elements peut etre realise avec une complexité en O(1)
 
3/Pour un tableau dentier quelconques de taille n,la plus grande difference en valeur absolue entre 2 elements peut etre une realise avec une complexite en O(log2n)
 
4/Pour un tbaleau dentier trié de taille n,la plus petite difference en valeur absolue entre 2 elements peut etre realise avec une complexite en O(n)
 
voila

1/ non
2/ parce que suffit de soustraire le premier du dernier
3/ parce qu'il faut chercher les extremes
4/ parce qu'il faut parcourir tout le tableau et calculer tab[i]-tab[i-1]

Merci kango,mais si cest possible des petites epxlication ca serait bien
jai des explication mais je sais pas si elle sont juste:
1/Cest a cause du fait que si le tableau nest pas trie,on sera peut etre obliger de parcourir tout le tableau,donc la complexite dans le plus mauvais cas sera proportionelle a la taille du tableau donc a n,et si on a un tableau trie,on peut chercher plus intelligemment grace a une recherche par dichotomie par exemple?
 
2/Car cette operation ne depend pas de la taille du tableau,donc elle en O(1)?
 
3/La par contre jai vraiment pas compris,je vois pas comment on arrive a un log2(n)?et pkoi log2 et pas log10?
 
4/la cest clair
 
voila,aussi si tas des autres exemple en log2n?

bha c'etait pas un mechant exercice
et en plus il comprend, il a juste demander confirmation d'apres ce qu'il a ecrit

(en plus il manque un truc à ta réponse à la 3...)

mmh ??

Il semblerait qu'il faille répondre vrai ou faux, à la base...

ah oui tien

en fait toutes les rpeonses que kangoo a donne je les  
connaisait cest surtout des explication pour la question  
3 que je veut

D'après toi quelle est la réponse? vrai ou faux?

je sais pas,jai aucune idee,je vois pas comment on peut fair eintervenir un log2n

Je repose la question dans l'autre sens : Pour toi, c'est quoi la complexité minimum pour ce problème?

le complexite minimum cets que le tableau soit ranger,donc onest dans le cas precedent,la,faut pas parcourir le tableau au moins une fois en entier pour reperer le plus grand et le plus petit element?mais on serait en O(n)

...donc la réponse à la question 3 est...?

O(n)?

 
Non, "faux", parce-que O(n)!
 

non la je sais vraiment plus,si tas une question indice qui puisse me faire rapprocher de la soluce

Mais tu l'as la solution!!
Pour trouver la plus grande différence entre 2 éléments d'un tableau non trié on est obligé de parcourir tout le tableau...donc la complexité est O(n), donc la proposition numéro 3 est fausse.

 
Un indice : KangOl s'est planté sur le 3)

Non, il a juste oublié de dire que c'était faux avant de dire pourquoi...

oui et non
 
ce que j'ai dit juste mais repond pas a la question

dans quel cas on aura un log2n?

Pour cette question, jamais.

non enfin par exemple pkoi ce script on a :
 
while ( low <= high ) {
  mid = ( low + high ) / 2;
 
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}
 
est en log2n?

parce que c'est une recherche optimisée (me rappele plus le nom)

Parce-que c'est une dichotomie, tu ne parcours pas tous les éléments...déroule le fonctionnement, tu devrais comprendre le log2 facilement.

Parce que tu divises en 2 parties ton probleme a résoudre ! Cela revient comme de rechercher dans un arbre binaire. A chaque fois que tu sais si ton element est plus petit ou plus grand que celui du milieu, tu parts soit a gauche soit a droite dans ton arbre de recherche. Et quand tu dessine ton arbre binaire (a exactement deux fils) de recherche sur papier, tu te rends compte que tu arrive très vite aux feuilles. Tu remarqueras meme que la hauteur de l'arbre binaire est exactement de log base 2 de n (log2(n)) ... le deux veut bien dire que tu divises en 2 ton probleme de recherche ! si tu le diviserais en 10, tu serais en log base 10 de n (log10(n))...ce qui n'ameliore pas enormement la rapidité de ton algorithme c'est pour cela que l'on parle ordre de grandeur en complexité algorithmique. Dans ce cas un log base X de n reste de complexité de log (n).
Voila