Vereinfachen Sie die Komplexität von n Multichoose k

11

Ich habe einen rekursiven Algorithmus mit einer zeitlichen Komplexität, die der Auswahl von k Elementen aus n mit Wiederholung entspricht, und ich habe mich gefragt, ob ich einen vereinfachten Big-O-Ausdruck erhalten könnte. In meinem Fall kann k größer als n und sie wachsen unabhängig voneinander.

Insbesondere würde ich einen expliziten Exponentialausdruck erwarten. Das Beste, was ich bisher finden konnte, ist das basierend auf Stirlings Näherung O(n!)O((n/2)n) , also kann ich das verwenden, aber ich habe mich gefragt, ob ich etwas Schöneres bekommen könnte.

O((n+k1k))=O(?)

yoniLavi
quelle
Dies ist nicht gerade sehr hilfreich, aber sehr interessant Ramanujans faktorielle Annäherung
Pratik Deoghare
Danke, sieht nach einer coolen Annäherung aus, scheint aber in der Tat nicht zu helfen, dies zu vereinfachen. n!π(ne)n8n3+4n2+n+1306
YoniLavi

Antworten:

6

Bearbeiten: Diese Antwort ist für . Ohne k in Bezug auf n zu begrenzen, ist der Ausdruck unbegrenzt.k<nkn

Wenn ist, wird Ihr Ausdruck zu O ( ( 2 ( n - 1 )).k=n1. Beachten Sie, dass nach Stirlings Formel für jede0<α<1(mO((2(n1)n1))0<α<1 wobeiH(q)=-qlogq-(1-q)log(1-q)ist die binäre Entropie. InsbesondereH(1/2)=1. Deshalb haben wir fürk=n-1

(mαm)=Θ(m1/22H(α)m),
H(q)=qlogq(1q)log(1q)H(1/2)=1k=n1
O((2(n1)n1))=Θ((2n2)1/222n2)=Θ(4nn).

Da die Obergrenze der schlechteste Fall ist (ich lasse es als Übung, um dies zu zeigen), ist Ihr Ausdruck O ( 4 nk=n1.O(4nn)

A.Schulz
quelle
Danke, genau das, wonach ich gesucht habe! und es ist noch eine andere Sache, die mich motiviert, Informationstheorie zu studieren.
YoniLavi
@ Falcor84: Ich hatte im letzten Übergang einen kleineren Tippfehler. Der Quadratwurzelteil muss zum Nenner gehen. Daher ist die Grenze etwas besser als die von Paresh. (Eigentlich ist die Grenze asymptotisch eng.)
A.Schulz
Ich hätte auch dieses kleine Minuszeichen bemerken sollen, nochmals vielen Dank.
YoniLavi
Ihre Aussage "Links als Übung", dass der schlimmste Fall ist, ist falsch. Wenn n = 3 ist , lautet der Ausdruck (k=n1n=3 . Dies ist nicht immer weniger als ( 4(k+2k)=(k+22)=(k+1)(k+2)2. (42)=6
Peter Shor
1
Da (n+k1k)=(n+k1n1) ist das Problem in symmetrischn and k (which can grow without relation in my case). Therefore, I suppose, the more accurate answer would be to replace n in the final part of the answer with x:=max(n,k)
yoniLavi
2

Wolfram says Sondow (2005)[1] and Sondow and Zudilin (2006)[2] noted the inequality:

14rm[(r+1)r+1rr]m<((r+1)mm)<[(r+1)r+1rr]m
for m a positive integer and r1 a real number.

We can then use

(n+k1k)<(n+kk)=((r+1)mm)
with r=nk and m=k.

Then we have

(n+k1k)<[(r+1)r+1rr]m=(n+kk)n+k

Now, the binomial expression has the highest value at the middle of the Pascal's triangle. So, in our case, n+k=2k or at k=n.

Substituting that in the above inequality, we get:

(n+k1k)<22n=4n
.

Therefore, a tighter bound is

(n+k1k)=O(4n)
.

You can also see that the lower bound for the maximum value is

(n+k1k)=Ω(4nn)

References:
[1] Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.
[2] Sondow, J. and Zudilin, W. "Euler’s constant, q-logarithms, and formulas of Ramanujan and Gosper" Ramanujan J. 12, 225-244, 2006.

Paresh
quelle