Was ist die zeitliche Komplexität dieses Algorithmus? Und warum?

Ich bin festgefahren, wenn ich die zeitliche Komplexität des folgenden Algorithmus analysiere:

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)

Der Root-Aufruf wird fun (0, 0, n, n)und nist die Größe des Problems.

Ich denke das: Die Wiederholungsrelation ist $T(n, n) = T(n-1, n) + T(n, n-1)$ , was $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$ und somit $O(2^m) \iff O(4^n)$ .

Ist meine Analyse korrekt (ich weiß, dass sie nicht sehr vollständig und genau ist)? Wenn es einen schwerwiegenden Fehler gibt, weisen Sie bitte darauf hin oder zeigen Sie mir einen korrekten und vollständigen Beweis für die zeitliche Komplexität dieses Algorithmus.

algorithm-analysis runtime-analysis 象嘉道
quelle

xando, ich ermutige Sie, die Frage zu bearbeiten, um zu erklären, warum die Standardtechniken nicht funktionieren: Erklären Sie, warum sie fehlschlagen. (Cc: @YuvalFilmus) Erhalten Sie beispielsweise eine Wiederholungsbeziehung, die schwer zu lösen ist, und wenn ja, welche Wiederholung erhalten Sie?

In Kommentaren mit Polyergic habe ich festgestellt, dass der Pseudocode unklar ist: Es ist nicht klar, was Sie mit dem Algorithmus meinen, wenn sowohl d>0als auch p>0. Sie zeigen nicht, was die Funktion zurückgibt, wenn wir die 3. und 4. if-Anweisung erreichen. Wollten Sie returnnach jedem rekursiven Aufruf von eine Anweisung haben fun? (Wollten Sie fun (r, k + 1, d - 1, p)es sein return fun (r, k + 1, d - 1, p)?) Oder wollten Sie eine returnAussage ganz am Ende des Funktionskörpers haben? Bitte bearbeiten Sie Ihren Pseudocode, um zu verdeutlichen und sicherzustellen, dass Sie zeigen, was dies in allen möglichen Fällen zurückgibt.

Um es auf eine andere Weise: annehmen d<=pund d>0und p>0alle halten. Was soll passieren? Führt der Algorithmus zwei rekursive Aufrufe der Funktion durch? Oder ruft es rekursiv auf fun(r, k + 1, d - 1, p)und kehrt dann sofort zurück, ohne rekursiv aufzurufen fun(r, k - 1, d, p - 1)? Wenn ich Ihren Pseudocode wörtlich nehme, scheint es, dass er zwei rekursive Aufrufe ausführt und dann mit einem undefinierten Rückgabewert zurückkehrt - aber das scheint seltsam und lässt mich fragen, ob der Pseudocode einen Tippfehler enthält.

Antworten:

$d$ $p$ $d,p \geq 0$ $d \leq p$ $(d,p)$ $(d-1,p),(d,p-1)$ Vermeiden von Paaren, die die oben angegebenen Einschränkungen ungültig machen.

$(0,0)$ $p$ $d$ $d \leq p$ $n$ $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$

Um eine Obergrenze zu erhalten, beachten Sie, dass wir auf dem Weg zu jedem Blatt durch Knoten gehen und dies eine Obergrenze ergibt, die größer ist als die Untergrenze, dh . $2n$ $2n$ $\Theta(4^n/\sqrt{n})$

Wir haben eine Untergrenze von und eine Obergrenze von . Was sind die genauen Asymptotika? Sie wachsen wie die Gesamtzahl der Pfade, die die X-Achse nicht kreuzen und höchstens Schritte in jede Richtung aufweisen. Unter Verwendung des Wahlsatzes von Bertrand können wir einen genauen Ausdruck dafür erhalten: Es bleibt also, diese Summe asymptotisch zu schätzen: $\Omega(4^n/n^{3/2})$ $O(4^n/\sqrt{n})$ $n$

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

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

\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{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
quelle

Ich mag Ihren geometrischen Ansatz mit diesen "Schritten" sehr. Ist das eine übliche Technik? Ich habe es noch nie gesehen.

Andreas T

@AndreasT Ich würde es nicht als übliche Technik bezeichnen, normalerweise trifft es nicht zu. Hier ist die kombinatorische Interpretation ziemlich offensichtlich und führt zu einer solchen Lösung.

Yuval Filmus

Von Fall zu Fall:

d> p : Konstante Zeit
d = 0 ∧ p = 0 : Konstante Zeit
d> 0 : Man beachte, dass d ≯ p ist, also haben wir 0 <d ≤ p und funrekursiert auf d-1 bis d ≯ 0; da p> 0 ist, ist dies in d + linear (Fall 4) .
p> 0 : Man beachte, dass d ≯ 0 ist, also haben wir d ≤ 0 ≤ p (mit d <p) und funrekursiv auf p-1 bis p ≯ 0; Dies ist linear in p + (einer von Fall 1, 2 oder 5).
d ≤ p <0 : undefiniert; Ich gehe davon aus, dass dies konstante Zeit ist

Beginnend mit d = p = n> 0 trifft Fall 3, gefolgt von Fall 4. Wenn n eine ganze Zahl ist, ist der letzte Fall 2, andernfalls ist der letzte Fall 5. Die Gesamtzeit für diese Fälle ist d + p +1 oder 2n + 1.

ShadSterling
quelle

2n. Ich denke, Sie haben abgelehnt, weil ich mich auf die Argumentation konzentriert habe?

ShadSterling

Vielen Dank für die Bearbeitung der Antwort! Das Rätsel ist nun, dass Sie zu dem Schluss gekommen sind, dass die Laufzeit , aber Yuval zu dem Schluss gekommen ist, dass die Laufzeit in exponentiell ist . Das ist ein ziemlich wesentlicher Unterschied.

O (n)

$O(n)$

n

$n$

Hmm, ich denke, ich habe die Pseudocodes ifals "mach eine davon" genommen, während @Yuval sie als "jede dieser in der richtigen Reihenfolge betrachten" nahm. Letzteres ist natürlich das, was ifs (ohne else) im tatsächlichen Code bedeutet; Ich bin an Ersteres in fast jedem anderen Kontext als dem eigentlichen Code gewöhnt (auch im Pseudocode, obwohl die Verwendung im Pseudocode inkonsistent ist).

ShadSterling

Ich verstehe was du meinst. Das Fehlen von returnAnweisungen in der zweiten Hälfte des Codes macht dies ziemlich verwirrend.