Rozwiązywanie relacji rekurencji z √n jako parametrem

18

Rozważ powtórzenie

$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$

dla z pewną stałą dodatnią , a . $n \gt 2$ $c$ $T(2) = 1$

Znam twierdzenie Master dotyczące rozwiązywania nawrotów, ale nie jestem pewien, w jaki sposób moglibyśmy rozwiązać tę relację za pomocą tego. Jak podchodzisz do parametru pierwiastka kwadratowego?

asymptotics recurrence-relation master-theorem

— poszukiwacz
źródło

5

Twierdzenie Master nie ma tutaj zastosowania;

\sqrt{n}

$\sqrt{n}$ nie może być zapisane jako

\frac{n}{b}

$\frac{n}{b}$ . Co jeszcze próbowałeś?

— Raphael

@Raphael: Próbowałem metody substytucji, ale wydawało mi się, że utknąłem na wartości, którą powinienem zastąpić.

— poszukujący

1

A może „rozłóż kilkakrotnie nawrót, obserwuj wzór, zgadnij rozwiązanie i udowodnij ”?

— Raphael

Cóż, to pierwsze tego typu spotkanie, może jakaś pomoc pomoże mi z łatwością rozwiązać przyszłe problemy natury.

— osoba poszukująca

Ponieważ wspomniałeś Twierdzenie o Mistrzu, zakładam, że musisz rozwiązać tę relację dla granic asymptotycznych i tak naprawdę nie potrzebujesz wyrażenia formy zamkniętej. Biorąc pod uwagę poniżej, istnieje kilka dobrych rozwiązań dla znalezienia wyrażenia formy zamkniętej, które nadają również asymptotyczną złożoność. Jeśli jednak potrzebujesz tylko asymptotycznej złożoności, analiza jest prostsza. Zajrzyj tutaj, aby znaleźć dobre wyjaśnienie dotyczące znajdowania asymptotycznych złożoności, z przyjemnym intuicyjnym rozwiązaniem dla Twojego problemu.

— Paresh,

9

Skorzystamy z sugestii Rafaela i rozwiążemy powtórkę. Poniżej wszystkie logarytmy są podstawą 2. Otrzymujemy

gdzieto ile razy musisz wziąć pierwiastek kwadratowy, aby zacząć od n, i osiągnąć 2. Okazuje się, że. Jak to widzisz? Zastanów się:

\begin{aligned} T (n) & = n^{1 / 2} T (n^{1 / 2}) + c n \\ = n^{3 / 4} T (n^{1 / 4}) + n^{1 / 2} c n^{1 / 2} + c n \\ = n^{7 / 8} T (n^{1 / 8}) + n^{3 / 4} c n^{1 / 4} + 2 c n \\ = n^{15 / 16} T (n^{1 / 16}) + n^{7 / 8} c n^{1 / 8} + 3 c n \\ \dots \\ = \frac{n}{2} T (2) + c n β (n) \end{aligned} .

$\begin{align*} T(n) &= n^{1/2} T(n^{1/2}) + cn \\ &= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\ &= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\ &= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\ & \ldots \\ &= \frac{n}{2} T(2) + c n \beta(n) \end{align*}.$

β (n)

$\beta(n)$

β (n) = \log \log n

$\beta(n) = \log \log n$

Więc ile razy musisz wziąć pierwiastek kwadratowy, aby osiągnąć 2, to rozwiązanie

\begin{aligned} n & = 2^{\log n} \\ n^{1 / 2} & = 2^{\frac{1}{2} \log n} \\ n^{1 / 4} & = 2^{\frac{1}{4} \log n} \\ \dots \end{aligned}

$\begin{align*} n &= 2^{\log n}\\ n^{1/2} &= 2^{\frac{1}{2} \log n} \\ n^{1/4} &= 2^{\frac{1}{4} \log n} \\ \ldots \end{align*}$

, czyli

. Tak więc rozwiązaniem rekurencji jest

\frac{1}{2^{t}} \log n \approx 1

$\frac{1}{2^t} \log n \approx 1$

\log \log n

$\log \log n$

. Aby uczynić to absolutnie rygorystycznym, powinniśmy zastosować metodę substytucji i bardzo uważać na to, jak się to zaokrągli. Kiedy będę miał czas, spróbuję dodać te obliczenia do mojej odpowiedzi.

c n \log \log n + \frac{1}{2} n

$c n \log \log n + \frac{1}{2}n$

— Peter Shor
źródło

„Trzeba wziąć pierwiastek kwadratowy

razy” - to można oczekiwać, że początkujący, aby zobaczyć, że coś? Ponadto twój wynik nie pasuje do wyników Yuvala; czy ma to być wyłącznie asymptotycznie?

\log \log n

$\log\log n$

— Raphael

@Raphael: Yuval popełnił błąd, który teraz poprawił. Wyjaśnię pierwiastek kwadratowy w mojej odpowiedzi.

— Peter Shor

3

Kolejny pomysł, aby zobaczyć, że rekurencja zajmuje

jest następujący: Biorąc pierwiastek kwadratowy z

, zmniejszasz o połowę cyfry potrzebne do binarnej reprezentacji

. Więc twoje wejście potrzebuje

bitów i dzielisz rozmiar słowa przez 2 dla każdego poziomu rekurencji. Dlatego zatrzymujesz się po

kroków.

O (\log \log n)

$O(\log\log n)$

n

$n$

n

$n$

w = \log n

$w=\log n$

\log w = \log \log n

$\log w=\log\log n$

— A.Schulz

10

W swoim komentarzu wspomniałeś, że próbowałeś zastąpienia, ale utknąłem. Oto pochodna, która działa. Motywacją jest to, że chcielibyśmy się pozbyć mnożnik po prawej stronie, pozostawiając nam coś, co wygląda jak $\sqrt{n}$ . W tym przypadku wszystko działa bardzo ładnie: $U(n) = U(\sqrt{n}) + something$

Teraz uprośćmy jeszcze bardziej, przechodząc do logów (od

\begin{aligned} T (n) & = \sqrt{n} T (\sqrt{n}) + n & so, dividing by n we get \\ \frac{T (n)}{n} & = \frac{T (\sqrt{n})}{\sqrt{n}} + 1 & and letting n = 2^{m} we have \\ \frac{T (2^{m})}{2^{m}} & = \frac{T (2^{m / 2})}{2^{m / 2}} + 1 \end{aligned}

$\begin{align} T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by $n$ we get}\\ \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting $n = 2^m$ we have}\\ \frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1 \end{align}$

). Niech

\lg \sqrt{n} = (1 / 2) \lg n

$\lg \sqrt{n} = (1/2)\lg{n}$

Aha! Jest to dobrze znany nawrót z rozwiązaniem

Powrót do

\begin{aligned} S (m) & = \frac{T (2^{m})}{2^{m}} & so our original recurrence becomes \\ S (m) & = S (m / 2) + 1 \end{aligned}

$\begin{align} S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\ S(m) &= S(m/2)+1 \end{align}$

S (m) = Θ (\lg m)

$S(m)=\Theta(\lg m)$

, mamy wtedy, gdy

(a więc

),

T ()

$T(\,)$

n = 2^{m}

$n=2^m$

m = \lg n

$m=\lg n$

\frac{T (n)}{n} = Θ (\lg \lg n)

$\frac{T(n)}{n} = \Theta(\lg\,\lg n)$

T (n) = Θ (n \lg \lg n)

$T(n) =\Theta(n\,\lg\,\lg n)$

— Rick Decker
źródło

6

$m=\log n \space$ $T(m) = {m \over 2}\cdot T({m\over 2}) + c\cdot 2^m\space$

$O(\log m)$ $O(2^m)\space$ $O((\log m) \cdot 2^m)\space$ $O(n \cdot \log \log n)\space$ dla $n$ .

W sumie, kiedy widzisz $\sqrt n$ lub $n^{a \over b}, a<b \space$ , dobrze jest sprawdzić logarytm.

_{PS: Pewny dowód powinien zawierać więcej szczegółów, pominąłem je.}

2

Postępujmy zgodnie z sugestią Rafaela $n = 2^{2^k}$ :

\begin{aligned} T (n) = T (2^{2^{k}}) & = 2^{2^{k - 1}} T (2^{2^{k - 1}}) + c 2^{2^{k}} \\ = 2^{2^{k - 1} + 2^{k - 2}} T (2^{2^{k - 2}}) + c (2^{2^{k}} + 2^{2^{k}}) \\ = \dots \\ = 2^{2^{k - 1} + 2^{k - 2} + \dots + 2^{0}} T (2^{2^{0}}) + c (2^{2^{k}} + 2^{2^{k}} + \dots + 2^{2^{k}}) \\ = 2^{2^{k} - 1} + c k 2^{2^{k}} \\ = (c \log \log n + 1 / 2) n . \end{aligned}

$\begin{align*} T(n) = T(2^{2^k}) &= 2^{2^{k-1}} T(2^{2^{k-1}}) + c2^{2^k} \\ &= 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) + c(2^{2^k} + 2^{2^k}) \\ &= \cdots \\ &= 2^{2^{k-1}+2^{k-2}+\cdots+2^0} T(2^{2^0}) + c(2^{2^k} + 2^{2^k} + \cdots + 2^{2^k}) \\ &= 2^{2^k-1} + ck2^{2^k} \\ &= (c\log\log n + 1/2)n. \end{align*}$

Edit: Thanks Peter Shor for the correction!

— Yuval Filmus
źródło

How did you come up with

2^{2^{k}}

$2^{2^k}$ ? Note for OP: "

\dots

$\dots$ " is not a proof, you'll have to provide that still (usually by induction).

— Raphael

@Raphael: It's nearly a proof. You just need to show that it's also correct for numbers not of the form

2^{2^{k}}

$2^{2^k}$ .

— Peter Shor

Actually, the recurrence is only well-defined for numbers of the form

2^{2^{k}}

$2^{2^k}$ , since otherwise, at some point

\sqrt{n}

$\sqrt{n}$ wouldn't be an integer, and you'll never reach the base case

T (2)

$T(2)$ .

— Yuval Filmus

1

If this recurrence actually came from an algorithm, it would probably really be something more like

T (n) = ⌈ \sqrt{n} ⌉ T (⌈ \sqrt{n} ⌉) + c n

$T(n) = \lceil \sqrt{n} \rceil T(\lceil \sqrt{n} \rceil) + cn$ .

— Peter Shor

1

Unravel the recurrence once as follows:

\begin{aligned} T (n) & = & \sqrt{n} T (\sqrt{n}) + n \\ = & n^{1 / 2} (n^{1 / 4} T (n^{1 / 4}) + n^{1 / 2}) + n \\ = & n^{1 - 1 / 4} T (n^{1 / 4}) + 2 n . \end{aligned}

$\begin{align} T(n) &=& \sqrt{n}~ T(\sqrt{n}) + n \\ &=& n^{1/2} \big ( n^{1/4} ~ T(n^{1/4}) + n^{1/2}\big) + n \\ &=& n^{1-1/4}~ T(n^{1/4}) + 2n. \end{align}$

Continuing the unraveling for $k$ steps, we have that:

\begin{aligned} T (n) & = & n^{1 - 1 / 2^{k}} T (n^{1 / 2^{k}}) + k n . \end{aligned}

$\begin{align} \label{eqn:unrav} T(n) &=& n^{1-1/2^k} T(n^{1/2^k}) + kn. \end{align}$

These steps will continue until the base case of $n^{1/2^k} = 2$ . Solving for $k$ we have:

\begin{aligned} n^{1 / 2^{k}} = 2 \\ ⟹ & \log n = 2^{k} \\ ⟹ & k = \log \log n . \end{aligned}

$\begin{align} &&n^{1/2^k} = 2 \\ &\implies& \log n= 2^k \\ &\implies& k= \log \log n. \label{eqn:ksol} \end{align}$

Substituting $k=\log \log n$ into the unraveled recurrence, we have

\begin{aligned} T (n) = \frac{n}{2} T (2) + n \log \log n . \end{aligned}

$\begin{align} T(n) = \frac{n}{2} T(2) + n \log \log n. \end{align}$

— pC_
źródło

2

Could you rewrite your picture to MathJax? We discourage images with text as the answers.

— Evil

1

@PKG it seems like your edit is slightly different and also you explain steps, maybe you could answer on your own.

— Evil