Calcul de complexité

Modérateur : Michel Quercia

Répondre
Mariem202
Messages : 4
Enregistré le : dim. nov. 05, 2017 9:52 pm
Classe : MP

Calcul de complexité

Message par Mariem202 » mer. nov. 21, 2018 7:04 pm

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
Messages : 30
Enregistré le : ven. déc. 11, 2015 9:24 am

Re: Calcul de complexité

Message par left_shift » jeu. nov. 22, 2018 10:05 am

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).

Avatar du membre
Der RHDJ
Messages : 1850
Enregistré le : sam. avr. 12, 2014 11:26 pm
Classe : Jône
Localisation : Boue

Re: Calcul de complexité

Message par Der RHDJ » jeu. nov. 22, 2018 8:23 pm

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.
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or

Avatar du membre
siro
Messages : 3214
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: Calcul de complexité

Message par siro » jeu. nov. 22, 2018 9:19 pm

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).)
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

left_shift
Messages : 30
Enregistré le : ven. déc. 11, 2015 9:24 am

Re: Calcul de complexité

Message par left_shift » ven. nov. 23, 2018 2:44 pm

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.

Avatar du membre
Der RHDJ
Messages : 1850
Enregistré le : sam. avr. 12, 2014 11:26 pm
Classe : Jône
Localisation : Boue

Re: Calcul de complexité

Message par Der RHDJ » ven. nov. 23, 2018 3:48 pm

C'est moi ou tu es un peu agressif Bobby ?
Mariem202 a écrit :
mer. nov. 21, 2018 7:04 pm
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.
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or

Errys
Messages : 258
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

Re: Calcul de complexité

Message par Errys » ven. nov. 23, 2018 4:28 pm

EDIT: déjà répondu.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-?

V@J
Messages : 2839
Enregistré le : jeu. janv. 22, 2009 6:15 pm

Re: Calcul de complexité

Message par V@J » mar. déc. 04, 2018 12:52 am

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

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité