Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Mais aussi sur les technos front comme React, Angular, Typescript et Javascript en général.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

Complexité d'un algorithme récursif

0 votes

Comment doit-je calculer la complexité d'un algorithme récursif ?
En particulier, je doit calculer la complexité de celui ci :

def guerrier(jour, monstres, pv=10, gold=0, chemin=""):
    if jour >= len(monstres):
        return jour, monstres, pv, gold, chemin
    else:
        # Cas du repos.
        pv_repos = pv + 5 if pv <= 5 else 10
        repos = guerrier(jour+1, monstres, pv_repos, gold, chemin + "A")
        # Cas de l'attaque.
        atq = [0, 0, 0, -1] # J'initialise l'attaque afin d'être sûr de comparer.
        if pv > monstres[jour].force:
            gold_atq = gold + monstres[jour].gold
            pv_atq = pv - monstres[jour].force
            atq = guerrier(jour+1, monstres, pv_atq, gold_atq, chemin + "F")
        return repos if repos[3] >= atq[3] else atq
demandé 12-Avr par Andy (274 points)

1 Réponse

+2 votes
 
Meilleure réponse

Disclaimer : je n'y connais pas grand chose en complexité.

En considérant le pseudo-code suivant, qui a AFAIK le même comportement que la fonction de l'OP :

def f(n, m):
    if c1(n, m):
        return n, m
    first_call = f(decay(n), m)
    second_call = f(decay(n), decay(m)) if c2(m) else default_m_and_n
    return first_call if c3(first_call, second_call) else second_call

Qui peut, par exemple, être instanciée comme suit :

def f(n, m):
    if n < m:
        return n, m
    first_call = f(n-1, m)
    second_call = second_call = f(n-1, m+n) if m % 2 == 0 else 1, 0
    return first_call if second_call[1] < first_call[1] else second_call

Ici, on voit bien qu'un appel de la fonction déclenche 2 appels (1 dans le cas où c2 n'est pas vérifiée).

L'ordre de grandeur de la complexité temporelle est donc O(2^n), autrement dit exponentielle.


Maintenant, pour être plus précis, ça dépend beaucoup des conditions. Si c1 est du style n < 0, on est en exponentiel. Si il dépends de m et de n, c'est plus compliqué, puisqu'on peut avoir des branches entières qui se coupent, et qui de fait peuvent casser la complexité.

De la même manière, si c2 est souvent fausse, la complexité tombe en linéaire puisqu'un appel de fonction ne mène en général qu'à un seul autre appel.

La fonction de l'OP semble tomber dans le cas exponentiel, puisque jour doit atteindre une valeur qui n'est jamais modifiée durant l'exécution de la fonction.

répondu 13-Avr par lucas (2,028 points)
sélectionné 27-Avr par Andy
...