Was ist die Tiefe der Rekursion, wenn wir ein Array in aufteilen

7

Wir haben eine Funktion, die ein Array als Eingabe verwendet. Es zerlegt ein Array in Teile mit gleichen Größen, wobei die Größe des Subarrays ist. Es unterbricht jedes der Subarrays so lange, bis nur noch zwei Elemente darin sind. Was ist die Tiefe dieser Rekursion?log2(n)n

Beispiel des Prozesses:

Zuerst haben wir Elemente und teilen sie in Teile mit gleichen Größen auf. Jeder dieser Teile enthält Elemente. In der nächsten Rekursionsstufe werden wir jedes der Subarrays wieder in Teile mit gleichen Größen aufteilen . Diese enthalten nun Elemente in jedem von ihnen. Und wir brechen das Array auf diese Weise weiter auf, bis wir ein Subarray mit nur zwei Elementen erreichen.nlog2(n)nlog2(n)log2(nlog2(n))nlog2(n)log2(nlog2(n))

Hinko Pih Pih
quelle
Es ist leicht zu berechnen, nicht wahr? Versuchen Sie zum Beispiel n = 1.000.000. Tun Sie das von Hand, dann sollte es offensichtlich sein.
Gnasher729
1
@ gnasher729 es ist mir immer noch nicht klar ...
Hinko Pih Pih
Was ist log_2 (1.000.000)? Wenn Sie dann 1.000.000 Elemente in so viele gleich große Subarrays aufteilen, wie groß ist jedes? Was ist, wenn Sie es erneut tun?
Gnasher729
Ich werde das Array nicht jedes Mal in Teile aufteilen . Im ersten Schritt ja, aber dann werde ich es in und so weiter aufteilen . log2(1,000,000)log2(1,000,000log2(1,000,000))
Hinko Pih Pih
Sie haben gesagt, "wo n die Größe des Arrays ist", nicht "wo n die Größe des Subarrays ist". In der Praxis macht es wenig Unterschied.
Gnasher729

Antworten:

5

Sei und bezeichne mit die Anzahl der Anwendungen von , die erforderlich sind , um unter eine beliebige Konstante zu bringen. Einerseits und damit Um eine Obergrenze zu erhalten, beachten Sie, dass wir , solange , , und daher sind höchstens Iterationen erforderlich, um auf zu reduzieren . Das gleiche Argument gilt für die Reduzierung von auff(n)=n/logng(n)fnf(t)(n)n/logtn

g(n)loglognn=lognloglogn.
f(t)(n)nlogf(t)(n)(logn)/2log(logn)/2n=O(logn/loglogn)nnnn4und so weiter und daher (Hier ist dasselbe wie .) Beachten Sie, dass . Für große haben wir (sagen wir), und so Daher wird die Summe durch eine konvergente geometrische Reihe multipliziert, und wir schließen daraus, dass Insgesamt bekommen wir das
g(n)lognloglogn+lognloglogn+logn4loglogn4+.
=O()logn=12lognnloglogn23loglogn
lognloglogn23lognloglogn.
g(n)=O(lognloglogn).
g(n)=Θ(lognloglogn).
Mit mehr Arbeit können wir wahrscheinlich eine verfeinerte Schätzung wie
g(n)lognloglogn.

Yuval Filmus
quelle
Was bedeutet darstellen? t
Hinko Pih Pih
Es ist die Anzahl , wie oft Sie angewendet . f
Yuval Filmus
Ich kann nicht herausfinden, wie Sie aus der ersten Ungleichung erhalten haben. g(n)loglognn
Hinko Pih Pih
Durch Lösen der Gleichung . Hier ist meine "willkürliche" Konstante. n/logtn=11
Yuval Filmus
Jetzt verstehe ich nicht, wie Sie Iterationen von . Kannst du es mir bitte erklären? log(logn)/2nlogf(t)(n)(logn)/2
Hinko Pih Pih
2

Scheint, dass Sie sich auf iterierten Logarithmus beziehen, der auch als -Funktion bezeichnet wird. Diese Funktion gibt an, wie oft Sie den Logarithmus einer Zahl verwenden können, bis eine Zahl kleiner oder gleich 1 entsteht.log

Die -Funktion wächst sehr langsam. Es ist die Umkehrung der Tetration.log

Mehr davon finden Sie hier .

Victor Stafusa
quelle
2
Es ist nicht der iterierte Logarithmus. Zum Beispiel: Im ersten Schritt werde ich habenn Elemente und trennen Sie es in log2(n)Teile. In jedem Teil werde ich habennlog2(n). Das bedeutet, dass ich auf der nächsten Ebene keinen Logarithmus eines Logarithmus nehmen werde. Ich werde das Subarray in trennenlog2(nlog2(n)) Teile, die definitiv mehr als log2(log2(n)). Und dieses Muster geht weiter. Ich habe das Programm tatsächlich geschrieben und die Rekursionstiefe ist immer größer alslog2(log2(n)) und immer kleiner als log2(n).
Hinko Pih Pih
2

Sei n die Größe des Arrays. Sei k = log2 (n). Im ersten Schritt dividieren Sie durch k. Solange die Arraygröße größer als istn1/2dividieren Sie durch mehr als k / 2. Ich würde sagen, das ist O (log n / log log n).

(Das Aufteilen in k Teile erfordert immer log n / log k Aufteilungen. Sie haben nach dem Sonderfall k = log n gefragt, daher log n / log log n. Dann müssen Sie entscheiden, ob das Schrumpfen k einen Unterschied macht oder nicht.)

gnasher729
quelle
Die Größe des Subarrays ist jedoch geringer als n12irgendwann. Und selbst wenn das nicht wahr wäre, verstehe ich nicht, wie du dazu gekommen bistO(log2(n)log2(log2(n))).
Hinko Pih Pih
Ihre bearbeitete Antwort bietet eine gute Erklärung für eine Konstante k Aber hier kist nicht konstant, daher ist es immer noch nicht hilfreich.
Hinko Pih Pih
1

Alle folgenden Logarithmen bedeuten Logarithmus mit Basis 2, log2().


Nennen wir die in der Frage angegebene Funktion slog. ("Slog" kommt von s Plitting mit Log . Es kann auch " s Maller als Log " bedeuten .) In genauen Worten, slog auf N wird durch die folgenden Bedingungen definiert.

  • Basisfall, slog(1)=0 und slog(2)=1.
  • die Wiederholungsbeziehung, slog(n)=1+slog(nlogn) zum n>2.

Wir können den folgenden Satz über das asymptotische Verhalten von beweisenslog(n).

limn slog(n)lognloglogn=1.

Hier ist die Grundidee des Beweises.

limnlognloglognlognlognloglognlogn=limmmlogmmlogmlog(mlogm)=limmmlogmmlogmlogm+log(1logmm)=limm(logm)2+mlog(1logmm)(logm)(logm+log(1logmm))=limm(logm)2+m(logmm)(logm)(logm)=1

Logische Folge. slog(n)=Θ(lognloglogn).


Die gleiche Schlussfolgerung gilt, wenn wir definieren slog(x) zum x>1 mit slog(x)=1 zum 1<x2 und slog(n)=1+slog(nlogn).


Übung. Schreiben Sie den vollständigen Beweis vonslog(n)lognloglogn.

John L.
quelle
Das asymptotische Ergebnis sollte hier folkloristisch oder bekannt sein. Ich habe jedoch noch keine Referenz gefunden.
John L.