Calcul de complexité

[Mariem202]

Bonjour

je n'arrive pas à calculer la complexité opérationnelle moyenne de cet algorithme: (c'est un programme pour calculer l'élément majoritaire dans une liste l, c'est à dire l'élément dont le nombre d'apparitions dans la liste est strictement supérieur à n/2)

n est la longueur de la liste l

#argument: une liste l
#renvoie: le tuple (élément majoritaire,nombre d'apparitions) si l'élément majoritaire existe, et renvoie -1 sinon

Code : Tout sélectionner

def majo1(l):
    trouvé = False
    i=0
    while not trouvé and i<len(l):
        if nbrDe(l[i],l) * 2 > len(l): trouvé=True    # nbrDe() renvoie le nombre d'apparition de l(i) dans l
        else: i+=1
    if trouvé: return l[i],nbrDe(l[i],l)
    else: return -1

sachant que la complexité de nbrDe() est n

[left_shift]

Chacune des fonctions auxiliaires et opérations élémentaires sont utilisées au plus n fois par cet algorithme ; toutes sont de complexité constantes, à l'exception de la fonction nbrDe qui est de complexité linéaire O(n). La complexité totale est donc quadratique : en O(n^2).

[Der RHDJ]

Bah de fait je pense qu'elle est bien moindre puisque finalement il y a assez peu de cas où tu vas chercher loin dans la boucle while. I.e si jamais tu te trouves effectivement dans un cas où il existe un élément qui apparaît plus de la moitié du temps, à supposer que ses occurrences soient aléatoirement réparties dans l, tu te retrouves avec *approximativement* une chance sur deux de tomber dessus à chaque fois que tu testes une valeur.

Du coup on va avoir quelque chose bien en dessous du O(n^2), genre du O(n*log(n)) au pifomètre (genre le n sortirait de la complexité de la fonction nbrDe, et le log viendrait du i moyen jusque auquel il faudrait aller chercher(genre moralement si tu fais des calculs de probas tu vas pouvoir majorer un truc par une binomiale, du coup tu te retrouves avec du i en exposant, et bim boum en inversant c'est raisonnable de tomber sur du log)). D'ailleurs si jamais tu prends une liste triée en entrée, le problème peut se résoudre de façon complètement linéaire pour peu que tu te débrouilles correctement, donc franchement O(n*log(n)) c'est crédible.

Après j'ai pas fait info en prépa, tout aussi bien je m'emporte un peu je n'en sais rien.

[siro]

C'est au programme, la complexité moyen cas/pire cas ?

(Je suis quasi sûr qu'on a moins que du quadratique, probablement du n*log(n), à disposition. En pire cas, c'est quadratique, point. Je vais dans le sens de RHDJ, on peut se ramener à une complexité linéaire si la liste est déjà triée, et donc nlog(n).)

[left_shift]

Seule la complexité dans le pire des cas est au programme en classe préparatoire. La complexité de cet algorithme est quadratique dans le pire des cas ; il suffit de considérer un tableau de taille 2n+1 dont les n premiers éléments sont égaux à 0 et les n+1 suivants à 1.

Il existe bien entendu d'autres algorithmes de meilleure complexité pour résoudre ce problème, mais ça n'est pas la question posée. Par exemple, une stratégie diviser pour régner conduit à une complexité en n log n (en revanche, trier le tableau comme le proposent Der RHDJ et Siro n'apporte rien ; d'ailleurs pour être posé ce problème n'exige pas de relation d'ordre entre les éléments). Il existe aussi un algorithme de complexité linéaire un peu plus subtil ; j'imagine que toute personne ayant fait un peu d'algorithmique avancée l'a déjà rencontré, c'est un classique.

[Der RHDJ]

C'est moi ou tu es un peu agressif Bobby ?

je n'arrive pas à calculer la complexité opérationnelle moyenne de cet algorithme

Je maintiens mon n*log(n) de complexité moyenne en supposant qu'on prend en entrée des listes dans lesquelles un élément est majoritaire (et que son rang dans les éléments de la liste est aléatoire uniforme).

Du reste dans un cas discret comme ça, tu pourras toujours poser une relation d'ordre sur tes éléments et te ramener au cas où la liste est triée. Et une fois que la liste est triée, à supposer qu'un des éléments est majoritaire ce sera forcément l'élément médian (comme je l'ai précisé plus haut il faut adapter le code, c'est certain qu'en le reprenant texto ça ne changeait rien).

Maintenant je ne connais pas les classiques (déso) mais il me semble que tu n'as pas à t'encombrer avec des algos subtils pour arriver à une complexité linéaire, tu peux te contenter d'un bail style:

Code : Tout sélectionner

for i in l:
	aux[i] = aux[i] + 1
	if aux[i] > len(l)/2:
		return i
return -1

Où moralement aux est comme une sorte de liste mais indexée par "les éléments de l", qui peuvent être n'importe quoi. Ça a l'air de se construire en temps linéaire.

[Errys]

EDIT: déjà répondu.

[V@J]

Bonsoir,

La complexité en moyenne est évidemment linéaire, puisque chaque élément du tableau à au moins une chance sur 2 d'appartenir à la classe majoritaire.

Pour un algo en temps linéaire (dans le pire des cas) et en mémoire constante (voire en log(n) si on veut s'amuser à compter le nombre de bits des entiers utilisés), on pourra commencer par identifier le seul élément majoritaire possible à l'aide de ce genre de sous-routine.

Cordialement,

V@J