svp comment je peux calculer la complixité de ce pôlynome :

a*alpha + b*alpha^2 + c*alpha^3+ ... + z*alpha^n

et merci

Je n'ai rien trouvé sur le web qui parle de "complexité" d'un polynome.
On parle généralement de "degré" d'un polynome.
Dans ce cas, il serait de degré  n

j'ai posé la même question dans des forums informatique, ils m'ont dit que cette question concerne maths ... bon !!! mon objectif est de calculer la complexité d'un algorithme qui retourne un polynome comme resultat. c-à-d je veux calculer son (Big O )

Si tu me disais ce que tu as comme information au départ et ce que tu veux obtenir comme résultat.
D'après ce que je comprend, la complexité est linéaire suivant la valeur de n.
Si tu veux évaluer la valeur numérique:
puissance = 1
evaluation = 0
pour i de 1 à n
    puissance = puissance * alpha
    evaluation = evaluation + coefficient[i] * puissance
fin
La complexité de ce calcul est de complexité O(n)

Aaaaah, la complexité de l'algorithme, pas du polynôme !!!

Je dirais O(n²), du moins dans sa version naïve où l'on recalcule chaque a^k, ce qui nécessite O(k) multiplications à chaque fois.

Ici, on a donc besoin de O(0) + O(1) + O(2) + ... + O(n) multiplications, soit O(1+2+...+n) = O(n²).

Par contre, la méthode de Horner est en O(n). Voir https://www.bibmath.net/dico/index.php?action=affiche&quoi=./h/horner.html

(Pierrot : tu as présenté l'algorithme de Horner, je crois, c'est bien ça ?)

-
Edité par robun 11 décembre 2021 à 12:17:57

Avec l'algo que j'ai mentionné, je ne fais qu'une multiplication de puissance par tour de boucle.
Je n'évalue pas alpha^i pour chaque valeur de i.
Je part des puissances les plus basses en allant vers les puissances les plus  élevées.
Pour sauter une puissance, il suffit que le coefficient soit nul.

Bonjour,

donc tu demandes la complexité d'un algo … ça c'est déjà bien lol

Mais la complexité en temps ? en espace ? par rapport à quelles données en entrée (les coef fixe + alpha variable, alpha fixé avec les coef variables ? tout fixé ? tout variable ?) 

Ton algo renvoie un polynôme pas une valeur … 

Il va falloir être vachement plus précis.

mon code en python est comme suit:

1- une fonction qui retourne des poids sous forme d'un tensor pytorch

def poids(n, alpha):
    w=torch.tensor([(alpha**i)*(1-alpha) for i in range(n)])
    return w

2- puis je multiplie chaque élément d'une liste par son poids :

n = 6
alpha = 0.5
Liste = Liste * poids(n, alpha) // Liste est un tensor pytorch qui contient des entiers

et moi je cherche la complexité temporelle de ce code (O)

-
Edité par Driss EL ALAOUI 12 décembre 2021 à 18:54:50

Là ce n'est plus la complexité d'un algo mais d'un code. On va supposer que tu veux la complexité temporelle en terme d'opérations élémentaires en fonction de la taille n à défaut de plus de précision.

Il va falloir consulter la doc pytorch pour connaître la complexité du constructeur tensor et de l'opérateur * sur tensor … sans ces infos tu ne sauras pas grand chose.

J'ai cherché partout, mais je n'ai rien trouvé.

Si on ignore la complexité du constructeur tensor dans pytorch, c'est quoi la complexité de ces operations dans ce code ?

-
Edité par Driss EL ALAOUI 15 décembre 2021 à 13:00:11

Bah il «suffit» d'en consulter le code → https://github.com/pytorch/pytorch/blob/master/torch/_tensor.py 

À nouveau, il faudrait connaître la complexité de la construction d'une liste en Python ⇒ https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt 

Tu as aussi une exponentiation … Et il y a tellement de facteurs (optimisation, cache, …)  qui rentrent en jeu que déterminer la complexité temporelle d'un code est une tâche ardue.

Après le plus simple est peut-être de timer un code en fonction de la taille des données d'entrée et d'en déduire sa complexité temporelle avec les points que tu auras mesurés.

ce que tu m'as dit est très difficile à réaliser

Quoi ? timer le bout de code :

def poids(n, alpha):
    w=torch.tensor([(alpha**i)*(1-alpha) for i in range(n)])
    return w

avec différentes valeurs de n ????

Comme c'est du python, pourquoi ne pas tenter de poser ta question dans le forum dédié ?

Je poste ma question dans le forum math, ils me disent de poster ce genre de question dans le forum dédié, et quand je la poste dans le forum python je trouve la même réponse !!!

mon probléme c'est que je veux savoir la complexité de mon code , est ce que: O(n) ? O(n^2) ? O(nlogn) ? ou O(n^k) ?

Bonjour Driss,

S'agit-il d'un exercice ? Si oui, le code t'est-il donné tel quel (cad avec l'utilisation de pytorch) ou est-ce toi qui l'a codé de cette façon ?

Et dans le deuxième cas ou si ce n'est pas un exercice, peut-être devrais-tu le coder différemment cad en utilisant des outils dont les complexités des opérations sont "mieux" renseignées (du genre simplement le type list ou des array numpy) parce que je ne connais pas pytorch mais ce que tu fais est facilement transposable sans l'utiliser et je pense que tu comprendras mieux la complexité en décomposant un peu plus ce qui se passe dans ton code.

En gros, écris l'algo en pseudo-code, calcule sa complexité, puis programme le et modifie ton calcul en fonction des complexité des opérations sur les listes ou array (mais m'est avis que ça ne changera pas ta complexité car l'accès aux éléments d'un array est constant - moins sûr pour les listes mais en gros ça doit être ça).

Driss EL ALAOUI a écrit:

[...]

mon probléme c'est que je veux savoir la complexité de mon code , est ce que: O(n) ? O(n^2) ? O(nlogn) ? ou O(n^k) ?

bah là tu as ta réponse … c'est juste qu'il va falloir bosser un peu pour la trouver !

White Crow a écrit:

Là ce n'est plus la complexité d'un algo mais d'un code. On va supposer que tu veux la complexité temporelle en terme d'opérations élémentaires en fonction de la taille n à défaut de plus de précision.

Il va falloir consulter la doc pytorch pour connaître la complexité du constructeur tensor et de l'opérateur * sur tensor … sans ces infos tu ne sauras pas grand chose.

Driss EL ALAOUI a écrit:

J'ai cherché partout, mais je n'ai rien trouvé.

[...]

White Crow a écrit:

Bah il «suffit» d'en consulter le code → https://github.com/pytorch/pytorch/blob/master/torch/_tensor.py 

À nouveau, il faudrait connaître la complexité de la construction d'une liste en Python ⇒ https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt 

Tu as aussi une exponentiation … Et il y a tellement de facteurs (optimisation, cache, …)  qui rentrent en jeu que déterminer la complexité temporelle d'un code est une tâche ardue.

Après le plus simple est peut-être de timer un code en fonction de la taille des données d'entrée et d'en déduire sa complexité temporelle avec les points que tu auras mesurés.

Après ça je pense que tu as tout en main … tu n'as pas forcément une réponse toute faite … Rien que pour l'exponentiation il va au moins falloir estimer les ordres de grandeur des nombres en jeu et avoir une idée de comment python le calcule …

Et quant à pytorch, pour savoir ce qui se passe, quelle sont les sdd utilisées, … il va falloir consulter le code (lien fourni).

Et attention la complexité temporelle d'un algo ne te donnera pas forcément une approximation du temps d'exécution d'un code pour les raisons que je te t'ai déjà fournies.

Driss EL ALAOUI a écrit:

Je poste ma question dans le forum math, ils me disent de poster ce genre de question dans le forum dédié, et quand je la poste dans le forum python je trouve la même réponse !!!

Ce n'est pas ce qui s'est passé ici. Tu as reçu des réponses, et de bonnes réponses (la suggestion de White Crow de chronométrer les calculs avec différentes valeurs de n – vraiment, fais-le !!!), mais tu as demandé d'autres réponses. C'est pour ces autres réponses qu'il t'est suggéré de demander à côté.

Bonjour sylpro

non ce n'est pas un exercice, mais c'est un tout petit morceau de mon code pour comparer plusieurs méthodes dans pytorch. J'ai fait une comparaison au niveau de la précision et je dois calculer la complexité de chacune.
bon voici mon code dans Numpy pour plus de clarté:

def poids(n, alpha):
    w=np.array([(alpha**i)*(1-alpha) for i in range(n)])
    return w

n = 6
alpha = 0.5
Liste = Liste * poids(n, alpha) // Liste est un tableau Numpy qui contient des entiers

mon grand problème c'est que je suis incapable de calculer la complexité, quelque soit le code !!

-
Edité par Driss EL ALAOUI 16 décembre 2021 à 12:34:41

Rien que pour le premier morceau :

def poids(n, alpha):
    w=np.array([(alpha**i)*(1-alpha) for i in range(n)])
    return w

Tu la creation d'une liste de n éléments ⇒ tu auras n x la complexité de création d'un élément

création d'un élément  ⇒ tu as le coût de l'exponentiation plus une multiplication plus une soustraction (ces deux dernières seront sans doute en O(1) mais ptêt pas l'exponentioation), il va falloir se renseigner sur le coût d'un exponentiation …

De cette liste tu crées un array avec numpy, il va falloir se renseigner sur le coût d'une telle création … sans doute O(n) mais va savoir c'est ptêt moins si la liste est réuilisée ou plus si d'autres trucs sont fait. Par exemple si l'array numpy est à croissance dynamique et suivant la taille de la liste ça ne sera que O(n) en temps amorti … ou moins si tu as peu de données et que l'interpréteur prends avantage du cache …

En algo un truc du genre :

liste ← ()
pour i de 0 à n-1 faire
    liste.ajouter( αⁱ(1-α) )
fin pour

Tu pourrais dire que si l'exponentiation est considérée en O(1) et que l'insertion dans la liste se fait également en temps constant alors l'algo est en O(n) …

Tu peux également faire autrement plutôt que de faire une exponentiation opur chaque élément, tu construis un liste de n éléments en assignant la première valeur à (1-α) et le suivant sera le précédent multiplié par α directement dans un array numpy … mais ptêt que c'est ce que l'interpréteur fait … va savoir …

La complexité va te donner un ordre de grandeur lorsque la taille des données va augmenter, mais elle ne te donnera jamais une estimation du temps que ton code va prendre à l'exécution. Pour cela il faut timer … et extrapoler à partir des datas que tu vas obtenir.

-
Edité par White Crow 16 décembre 2021 à 13:41:47