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? $\log_2(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. $n$ $\log_2(n)$ $\frac {n} {log_2(n)}$ $log_2(\frac {n} {log_2(n)})$ $\frac {\frac {n} {log_2(n)}} {log_2(\frac {n} {log_2(n)})}$

complexity-theory time-complexity asymptotics recursion mathematical-analysis 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 .

\log_{2} (1, 000, 000)

$\log_2 (1,000,000)$

\log_{2} (\frac{1, 000, 000}{\log_{2} (1, 000, 000)})

$\log_2(\frac {1,000,000}{\log_2 (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

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 auf $f(n) = n/\log n$ $g(n)$ $f$ $n$ $f^{(t)}(n) \geq n/\log^t n$

g (n) \geq \log_{\log n} n = \frac{\log n}{\log \log n} .

$g(n) \geq \log_{\log n} n = \frac{\log n}{\log \log n}.$

f^{(t)} (n) \geq \sqrt{n}

$f^{(t)}(n) \geq \sqrt{n}$

\log f^{(t)} (n) \geq (\log n) / 2

$\log f^{(t)}(n) \geq (\log n)/2$

\log_{(\log n) / 2} n = O (\log n / \log \log n)

$\log_{(\log n)/2} n = O(\log n/\log\log n)$

n

$n$

\sqrt{n}

$\sqrt{n}$

\sqrt{n}

$\sqrt{n}$

\sqrt[4]{n}

$\sqrt[4]{n}$ und 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) ≪ \frac{\log n}{\log \log n} + \frac{\log \sqrt{n}}{\log \log \sqrt{n}} + \frac{\log \sqrt[4]{n}}{\log \log \sqrt[4]{n}} + \dots .

$g(n) \ll \frac{\log n}{\log\log n} + \frac{\log \sqrt{n}}{\log\log \sqrt{n}} + \frac{\log \sqrt[4]{n}}{\log\log \sqrt[4]{n}} + \cdots.$

\cdot ≪ \cdot

$\cdot \ll \cdot$

\cdot = O (\cdot)

$\cdot = O(\cdot)$

\log \sqrt{n} = \frac{1}{2} \log n

$\log \sqrt{n} = \frac{1}{2} \log n$

n

$n$

\log \log \sqrt{n} \geq \frac{2}{3} \log \log n

$\log\log \sqrt{n} \geq \frac{2}{3} \log \log n$

\frac{\log \sqrt{n}}{\log \log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log \log n} .

$\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log\log n}.$

g (n) = O (\frac{\log n}{\log \log n}) .

$g(n) = O\left(\frac{\log n}{\log\log n}\right).$

g (n) = Θ (\frac{\log n}{\log \log n}) .

$g(n) = \Theta\left(\frac{\log n}{\log \log n}\right).$ Mit mehr Arbeit können wir wahrscheinlich eine verfeinerte Schätzung wie

g (n) \sim \frac{\log n}{\log \log n} .

$g(n) \sim \frac{\log n}{\log \log n}.$

Yuval Filmus
quelle

Was bedeutet darstellen?

t

$t$

Hinko Pih Pih

Es ist die Anzahl , wie oft Sie angewendet .

f

$f$

Yuval Filmus

Ich kann nicht herausfinden, wie Sie aus der ersten Ungleichung erhalten haben.

g (n) \geq \log_{\log n} n

$g(n) \geq \log_{\log n} n$

Hinko Pih Pih

Durch Lösen der Gleichung . Hier ist meine "willkürliche" Konstante.

n / \log^{t} n = 1

$n/\log^t n = 1$

1

$1$

Yuval Filmus

Jetzt verstehe ich nicht, wie Sie Iterationen von . Kannst du es mir bitte erklären?

\log_{(\log n) / 2} n

$\log_{(\log n)/2} n$

\log f^{(t)} (n) \geq (\log n) / 2

$\log f^{(t)}(n) \geq (\log n)/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 haben

n

$n$ Elemente und trennen Sie es in

\log_{2} (n)

$\log_2(n)$ Teile. In jedem Teil werde ich haben

\frac{n}{\log_{2} (n)}

$\frac {n}{\log_2(n)}$ . Das bedeutet, dass ich auf der nächsten Ebene keinen Logarithmus eines Logarithmus nehmen werde. Ich werde das Subarray in trennen

\log_{2} (\frac{n}{\log_{2} (n)})

$\log_2(\frac {n}{\log_2(n)})$ Teile, die definitiv mehr als

\log_{2} (\log_{2} (n))

$\log_2(\log_2(n))$ . Und dieses Muster geht weiter. Ich habe das Programm tatsächlich geschrieben und die Rekursionstiefe ist immer größer als

\log_{2} (\log_{2} (n))

$\log_2(\log_2(n))$ und immer kleiner als

\log_{2} (n)

$\log_2(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 ist $n^{1/2}$ dividieren 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

n^{\frac{1}{2}}

$n^\frac {1}{2}$ irgendwann. Und selbst wenn das nicht wahr wäre, verstehe ich nicht, wie du dazu gekommen bist

O (\frac{\log_{2} (n)}{\log_{2} (\log_{2} (n))})

$O(\frac {\log_2(n)} {\log_2(\log_2(n))})$ .

Hinko Pih Pih

Ihre bearbeitete Antwort bietet eine gute Erklärung für eine Konstante

k

$k$ Aber hier

k

$k$ ist nicht konstant, daher ist es immer noch nicht hilfreich.

Hinko Pih Pih

1

Alle folgenden Logarithmen bedeuten Logarithmus mit Basis 2, $\log_2(\cdot)$ .

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

Basisfall, $\operatorname{slog}(1)=0$ und $\operatorname{slog}(2)=1.$
die Wiederholungsbeziehung, $\operatorname{slog}(n)=1+ \text{slog}\left(\left\lceil\dfrac{n}{ \lceil\log n\rceil}\right\rceil\right)$ zum $n\gt2.$

Wir können den folgenden Satz über das asymptotische Verhalten von beweisen $\operatorname{slog}(n)$ .

lim_{n \to \infty} \frac{slog (n)}{\frac{\log n}{\log \log n}} = 1.

$\lim_{n\to\infty}\dfrac{\quad\text{ slog}(n)\quad}{\dfrac{\log n}{\log\log n}}=1.$

Hier ist die Grundidee des Beweises.

\begin{aligned} lim_{n \to \infty} \frac{\log n}{\log \log n} - \frac{\log \frac{n}{\log n}}{\log \log \frac{n}{\log n}} & = lim_{m \to \infty} \frac{m}{\log m} - \frac{m - \log m}{\log (m - \log m)} \\ = lim_{m \to \infty} \frac{m}{\log m} - \frac{m - \log m}{\log m + \log (1 - \frac{\log m}{m})} \\ = lim_{m \to \infty} \frac{(\log m)^{2} + m \log (1 - \frac{\log m}{m})}{(\log m) (\log m + \log (1 - \frac{\log m}{m}))} \\ = lim_{m \to \infty} \frac{(\log m)^{2} + m (- \frac{\log m}{m})}{(\log m) (\log m)} \\ = 1 \end{aligned}

$\begin{align} \lim_{n\to\infty}\frac{\log n}{\log\log n}-\frac{\log \frac n{\log n}}{\log\log \frac n{\log n}} &=\lim_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log(m-\log m)}\\ &=\lim_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log m + \log(1- \frac{\log m}m)}\\ &=\lim_{m\to\infty}\frac{(\log m)^2+ m\log(1- \frac{\log m}m)}{(\log m)(\log m+ \log(1- \frac{\log m}m))}\\ &=\lim_{m\to\infty}\frac{(\log m)^2+ m(-\frac{\log m}m)}{(\log m)(\log m)}\\ &=1 \end{align}$

Logische Folge. $\text{slog}(n)=\Theta\left(\dfrac{\log n}{\log\log n}\right)$ .

Die gleiche Schlussfolgerung gilt, wenn wir definieren $\text{slog}(x)$ zum $x>1$ mit $\text{slog}(x)=1$ zum $1\lt x\le 2$ und $\operatorname{slog}(n)=1+ \text{slog}\left(\dfrac{n}{ \log n}\right)$ .

Übung. Schreiben Sie den vollständigen Beweis von $\text{slog}(n)\sim \dfrac{\log n}{\log\log n}$ .

John L.
quelle

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

John L.

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

Antworten: