Quelle est la complexité temporelle de cet algorithme? Et pourquoi?

Je suis bloqué par l'analyse de la complexité temporelle de l'algorithme suivant:

def fun (r, k, d, p):
    if d > p:
        return r
    if d = 0 and p = 0:
        r <- r + k
        return r
    if d > 0:
        fun (r, k + 1, d - 1, p)
    if p > 0:
        fun (r, k - 1, d, p - 1)

L'appel racine sera fun (0, 0, n, n), et nest de la taille du problème.

Je suppose que: La relation de récurrence est , ce qui équivaut à , et donc . $T(n, n) = T(n-1, n) + T(n, n-1)$ $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$ $O(2^m) \iff O(4^n)$

Mon analyse est-elle correcte (je sais qu'elle n'est pas très complète et exacte)? S'il présente un défaut grave, veuillez le signaler ou me montrer une preuve correcte et complète de la complexité temporelle de cet algorithme.

algorithm-analysis runtime-analysis 象嘉道
la source

xando, je vous encourage à modifier la question pour expliquer pourquoi les techniques standard ne fonctionnent pas: expliquez pourquoi elles échouent. (Cc: @YuvalFilmus) Par exemple, obtenez-vous une relation de récurrence difficile à résoudre, et si oui, quelle récurrence obtenez-vous?

Dans les commentaires avec Polyergic, j'ai réalisé que le pseudocode n'est pas clair: ce n'est pas clair ce que vous voulez dire pour l'algorithme, quand les deux d>0et p>0. Vous ne montrez pas ce que la fonction retourne si nous atteignons les 3e et 4e instructions if. Vouliez-vous avoir une returndéclaration après chaque invocation récursive de fun? (vouliez-vous l' fun (r, k + 1, d - 1, p)être return fun (r, k + 1, d - 1, p)?) Ou vouliez-vous avoir une returndéclaration à la toute fin du corps de la fonction? Veuillez modifier votre pseudocode pour clarifier et assurez-vous de montrer ce que cela renvoie dans tous les cas possibles.

Pour le dire d'une autre manière: supposez d<=pet d>0et p>0tous tiennent. Que doit-il arriver? L'algorithme effectue-t-il 2 invocations récursives à la fonction? Ou invoque-t-elle récursivement fun(r, k + 1, d - 1, p)puis revient-elle immédiatement, sans invoquer récursivement fun(r, k - 1, d, p - 1)? Si je prends votre pseudocode littéralement, il semble qu'il effectue 2 invocations récursives puis retourne avec une valeur de retour non définie - mais cela semble étrange et me fait me demander s'il y a une faute de frappe / bogue dans le pseudocode.

Réponses:

Les deux seuls arguments pertinents pour l'analyse asymptotique sont et . Ces arguments satisfont (virtuellement) et (nous devons mélanger légèrement la logique dans la fonction pour obtenir ceci). À chaque point de l'exécution, vous prenez la paire actuelle puis appelez récursivement la fonction avec les paires , en évitant les paires qui invalident les contraintes énoncées ci-dessus . $d$ $p$ $d,p \geq 0$ $d \leq p$ $(d,p)$ $(d-1,p),(d,p-1)$

Nous pouvons représenter l'arbre d'appel résultant comme un chemin commençant à . Chaque fois que vous diminuez , ajoutez un pas /. Chaque fois que vous diminuez , ajoutez un \ step. La condition garantit que vous ne descendez jamais en dessous de l'axe X. De plus, vous avez un "budget" de pour chaque étape. Le nombre total de feuilles dans cet arbre d'appel est exactement le nombre catalan , et cela nous donne un borne inférieure du temps d'exécution de la fonction. $(0,0)$ $p$ $d$ $d \leq p$ $n$ $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$

Pour obtenir une limite supérieure, notez que sur le chemin de chaque feuille, nous traversons nœuds, ce qui donne une limite supérieure plus grande que la limite inférieure, c'est-à-dire . $2n$ $2n$ $\Theta(4^n/\sqrt{n})$

Nous avons une borne inférieure de et une borne supérieure sur . Quelles sont les asymptotiques exactes? Ils croissent comme le nombre total de chemins ne traversant pas l'axe X qui ont au plus pas dans chaque direction. En utilisant le théorème de vote de Bertrand, nous pouvons obtenir une expression exacte pour ceci: Il reste donc à estimer cette somme asymptotiquement: $\Omega(4^n/n^{3/2})$ $O(4^n/\sqrt{n})$ $n$

\sum_{0 \leq ré \leq p \leq n} \frac{p - ré + 1}{p + 1} (\binom{p + ré}{p}) .

$\sum_{0 \leq d \leq p \leq n} \frac{p-d+1}{p+1} \binom{p+d}{p}.$

\sum_{0 \leq ré \leq p \leq n} (\binom{p + ré}{p}) - \sum_{0 \leq ré \leq p \leq n} \frac{ré}{p + 1} (\binom{p + ré}{ré}) = \sum_{0 \leq ré \leq p \leq n} (\binom{p + ré}{p}) - \sum_{0 \leq ré \leq p \leq n} (\binom{p + ré}{p + 1}) = \sum_{p = 0}^{n} (\binom{2 p + 1}{p + 1}) - \sum_{p = 0}^{n} (\binom{2 p + 1}{p + 2}) = \sum_{p = 0}^{n} \frac{1}{p + 1} (\binom{2 p + 2}{p}) = Θ (\sum_{p = 0}^{n} \frac{4^{p}}{p^{3 / 2}}) = Θ (\frac{4^{n}}{n^{3 / 2}}) .

$\sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \frac{d}{p+1} \binom{p+d}{d} = \\ \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p+1} = \\ \sum_{p=0}^n \binom{2p+1}{p+1} - \sum_{p=0}^n \binom{2p+1}{p+2} = \\ \sum_{p=0}^n \frac{1}{p+1} \binom{2p+2}{p} = \Theta\left(\sum_{p=0}^n \frac{4^p}{p^{3/2}}\right) = \Theta\left(\frac{4^n}{n^{3/2}}\right).$

Yuval Filmus
la source

J'aime beaucoup votre approche géométrique en utilisant ces "étapes". Est-ce une technique courante? Je ne l'ai jamais vu auparavant.

Andreas T

@AndreasT Je n'appellerais pas cela une technique courante, en fait normalement elle ne s'applique pas. Ici, l'interprétation combinatoire est assez évidente, et elle conduit à ce type de solution.

Yuval Filmus

Cas par cas:

d> p : Temps constant
d = 0 ∧ p = 0 : Temps constant
d> 0 : Notez que d ≯ p, donc nous avons 0 <d ≤ p, et funrevient sur d-1 jusqu'à d ≯ 0; puisque p> 0, c'est Linéaire en d + (cas 4) .
p> 0 : Notez que d ≯ 0, donc on a d ≤ 0 ≤ p (avec d <p), et funrevient sur p-1 jusqu'à p ≯ 0; c'est linéaire en p + (un des cas 1, 2 ou 5)
d ≤ p <0 : non défini; Je suppose que c'est le temps constant

En commençant par d = p = n> 0 frappe le cas 3, qui est suivi par le cas 4. Si n est un nombre entier, le cas final est 2, sinon le cas final est 5. Le temps total pour ces cas est d + p +1 ou 2n + 1.

ShadSterling
la source

2n. Je suppose que vous avez voté contre parce que je me suis concentré sur le raisonnement?

ShadSterling

Merci d'avoir édité la réponse! Le casse-tête est maintenant que vous avez conclu que le temps de fonctionnement est , mais Yuval a conclu que le temps de fonctionnement est exponentiel en . C'est une différence assez substantielle.

O (n)

$O(n)$

n

$n$

Hmm, je pense que j'ai pris les pseudocodes ifpour "faire un de ceux-ci" tandis que @Yuval les a pris pour "considérer chacun d'eux dans l'ordre". Ce dernier est, bien sûr, ce que ifs (sans else) signifie dans le code réel; Je suis habitué à l'ancien dans presque tout autre contexte que le code réel (y compris dans le pseudocode, bien que l'utilisation dans le pseudocode soit incohérente).

ShadSterling

Je vois ce que tu veux dire. L'absence de returndéclarations dans la seconde moitié du code rend cela assez déroutant.