Sally (./33) :
Euh dire que la suite (appelle-la suite de Walters si tu veux, c'est pas une série ) a le bon comportement asymptotique et dire qu'elle est le meilleur majorant possible de la complexité (autrement dit que c'est un O(complexité dans le pire cas)) sont deux choses différentes...

En fait, je crois que je n’ai toujours pas compris la nuance entre « majorer la complexité » et « majorer la cardinalité » dans le cas qui nous intéresse (cf ./27).
Moi je veux juste calculer « quel est le nombre maximum d’opérations à N nombres si l’on ne sait absolument rien sur ces nombres ? »

Sally (./33) :
Sinon l'associativité signifie que dès que dans ton arbre tu as deux nœuds + ou × en relation père-fils tu peux les permuter, donc je ne vois pas ce qui te permet de penser que ça a moins d'influence s'il y a plus d'opérateurs : plus tu as d'opérateurs plus tu peux rencontrer cette relation... alors on pourrait penser que ça réduit la cardinalité d'un facteur constant (auquel cas ça ne change rien au O) mais la réduire d'un facteur qui tend vers 1, ça ne me semble pas très réaliste.

À mon avis (j’ai bien souligné le mot « intuitivement »), je ne pense pas que ce facteur soit constant.
Certes, quand N augmente, le nombre de relation qui font doublon par associativité augmente, mais pas comme 4^(N-1)×(2N-2)!/((N-1)!×2^(N-1)), je dirais (toujours intuitivement) que c’est plutôt avec une « complexité » de 4^(N-1)×N².

Sally (./33) :
pour les soustractions et les divisions on s'est contenté de dire qu'elles n'étaient définies que pour un seul ordre des nombres, donc on fait comme si ces opérateurs étaient commutatifs, ça n'a pas de rapport avec l'associativité ^^

Il me semble que si :

Ethaniel (./16) :
Certes, on pourra argumenter du fait que l’on ait envie de calculer (4-9)+12, avec donc un nombre intermédiaire négatif, mais quand on va calculer (12-9)+4, on trouvera de toute façon le même résultat, donc autant éliminer immédiatement les cas dont on sait qu’ils réapparaîtront sous une autre forme lors de la recherche exhaustive des cas possibles.

On joue, il me semble, sur l’associativité, pour dire que le calcul avec valeur intermédiaire négative pourra de toute façon être retrouvé autrement sans valeur négative.