Algorithme

[Manaus]

Bonjour!!

Je cherche une fonction qui représentera le mieux l'ordre temporelle de l'algorithme suivant. Je ne dois utiliser que "+" et "*" comme opérateur. Je ne sais pas du tout comment faire :mur:

AlgorithmeA( K1, K2, ..., Kn, x )
y <- K1
Pour i <- 2 à n
y = y * x + Ki
retourner y

Merci pour votre aide toujours précieuse :++:

[fatal_error]

hello,

scolairement tu dirais

Code: Tout sélectionner

AlgorithmeA( K1, K2, ..., Kn, x )
y <- K1
Pour i <- 2 à n
y = y * x + Ki
retourner y

assignation y<-K1 = 1 itération
pour i=2 à n... ca va faire n-1 itérations
y = y*x+Ki: une multiplication, une addition, une assignation, donc 3
la boucle fait donc 3*(n-1)

et donc ton algo est en o(3*(n-1)+1) (parce que ca représente au plus "près")

Maintenant, en vrai :
tu sais pas c'est quoi y, imagine y c'est un objet super gros.
quand tu copies y*x+Ki ca se fait tu copies un truc mega gros (du coup) et cette copie (operateur =) prend vachement plus de temps que faire la multiplication.
Au final, ca n'a donc pas de sens de dire l'affectation coute 1, alors que la multiplication aussi.

Du coup, tu finis par dire... on fait n-1 itérations, ce qui est de l'ordre de n et l'algorithme est en o(n)

[Manaus]

hello,

scolairement tu dirais

Code: Tout sélectionner

AlgorithmeA( K1, K2, ..., Kn, x )
y <- K1
Pour i <- 2 à n
y = y * x + Ki
retourner y

assignation y<-K1 = 1 itération
pour i=2 à n... ca va faire n-1 itérations
y = y*x+Ki: une multiplication, une addition, une assignation, donc 3
la boucle fait donc 3*(n-1)

et donc ton algo est en o(3*(n-1)+1) (parce que ca représente au plus "près")

Maintenant, en vrai :
tu sais pas c'est quoi y, imagine y c'est un objet super gros.
quand tu copies y*x+Ki ca se fait tu copies un truc mega gros (du coup) et cette copie (operateur =) prend vachement plus de temps que faire la multiplication.
Au final, ca n'a donc pas de sens de dire l'affectation coute 1, alors que la multiplication aussi.

Du coup, tu finis par dire... on fait n-1 itérations, ce qui est de l'ordre de n et l'algorithme est en o(n)

Merci beaucoup pour ta réponse je comprend mieux!!


J'ai un autre algorithme que je n'arrive pas à transformer en fonction en utilisant "mod" "+" et "-". Je ne sais pas comment traiter la boucle Si avec un mod?

AlgorithmeB( A1, A2, ..., An )
r <- 0
Pour i <- 1 à n
Si ( i mod 2 = 1 ) Alors
r <- r - Ai
Pour j <- i à n
Si ( j mod 2 = 0 ) Alors
r <- r + Aj
retourner r