Rozwiązywanie dziel i zdobywaj rekurencje, jeśli współczynnik podziału zależy od

Czy istnieje ogólna metoda rozwiązania problemu ponownego wystąpienia formularza:

$T(n) = T(n-n^c) + T(n^c) + f(n)$

dla $c < 1$ lub bardziej ogólnie

$T(n) = T(n-g(n)) + T(r(n)) + f(n)$

gdzie $g(n),r(n)$ są niektórymi funkcjami subliniowymi $n$ .

Aktualizacja : Przejrzałem linki podane poniżej, a także przejrzałem wszystkie relacje powtarzalności w notatkach Jeffa Ericksona . Ta forma nawrotu nie jest nigdzie dyskutowana. Metoda Akkra-Bazi ma zastosowanie tylko wtedy, gdy podział jest ułamkowy. Wszelkie przejmujące odniesienia będą doceniane.

proof-techniques recurrence-relation

— Plummer
źródło

Spróbuj wygenerować funkcje.

— saadtaame

Czy stosuje się metodę Akra-Bazzi ? Podaje tylko szacunki

O (\cdot)

$O(\cdot)$ , ale to może wystarczyć.

— vonbrand,

Ponieważ nie podejmowałeś wielu prób samodzielnego rozwiązania problemu, mamy trochę pracy. Pozwól, że skieruję cię do naszych pytań referencyjnych, które szczegółowo omawiają problemy podobne do twojego. Zapoznaj się z wymienionymi tam powiązanymi pytaniami, spróbuj rozwiązać problem ponownie i dokonaj edycji, aby uwzględnić próby wraz z napotkanymi problemami.

— Raphael

Sprawdź materiały informacyjne Toma Leightona w „Notatkach na temat lepszych twierdzeń mistrzowskich dotyczących nawrotów dziel i rządź”, są one dostępne w sieci. Być może możesz dostosować tam dowód Akra-Bazzi do swojej sprawy.

— vonbrand

@EngrStudent Funkcje generujące zostały zaproponowane w pierwszym komentarzu. :)

— Raphael

Załóżmy, że masz wznowę wykracza reale dodatnie.

T (n) = {\begin{cases} T (n - n^{c}) + T (n^{c}) + f (n) & n > 2 \\ 1 & otherwise \end{cases}

$T(n) = \begin{cases} T(n - n^c) + T(n^c) + f(n) & \text{n > 2} \\ 1 & \text{otherwise} \end{cases}$

Co możemy zrobić z tą funkcją? Cóż, niewiele, chyba że nałożymy na nią pewne struktury. Pochodzę z analizy numerycznej, która jest oparta na przepisach numerycznych, które w jakiś sposób działają, nawet jeśli podstawowy problem jest albo niewystarczająco gładki (nieważne, nadal rzucamy metodę Newtona na podzielone różnice) lub zbyt skomplikowany do analizy (sortuj tego typu problemu). Moja reakcja na te problemy polega na tym, aby wyciągnąć ręcznie założone założenia, trzymać kciuki i mieć nadzieję na najlepsze. W tym przypadku wydaje się, że daje stosunkowo dobre granice.

W szczególności chcę przyjąć dwa główne założenia. Jedno z tych założeń jest mniej lub bardziej bezpodstawne, ale bez niego nie zajedziemy daleko. Drugi ma nieco przyjemną wizualną intuicję, którą, miejmy nadzieję, grok, ale nadal jest bardziej ręczny niż cokolwiek innego.

Zakładam, że jest „gładkie”. Dość łatwo zauważyć, że nie wszędzie jest różniczkowalna. W rzeczywistości, nawet nie jest ciągły, ponieważ dla i $T(n)$ $T(n)$ $f(n) = \log(n)$ $c = \frac{1}{2}$ $\lim_{n \to 2^-} T(n) = 1$ $\lim_{n \to 2^+} T(n) = 2 + \ln 2$ $n \mapsto \sqrt{n}$ $n \mapsto n - \sqrt{n}$ $T(n)$ $n$ $2$ gdzieś na swojej trajektorii. To wiele nieciągłości, może nawet uruchomić funkcję Dirichleta za swoje pieniądze. Jeśli dochodzimy do punktu, w którym porównujemy zachowania funkcji z prototypowym przykładem funkcji nigdzie ciągłej, czy nie jest zabawne twierdzenie, że jest ona „gładka”? Okazuje się, że w praktyce skutki tych nieciągłości zmniejszają się asymptotycznie do tego stopnia, że twój wykres wygląda prawie gładko, gdy zmierza w kierunku nieskończoności! Dlatego proponuję, abyśmy odłożyli widły i po prostu spojrzeli w drugą stronę w tej sytuacji. W szczególności założę, że w dowolnym punkcie zainteresowania który jest wystarczająco daleko od źródła, $n$ $n$ $T(n)$ jest różnicowalny lub przynajmniej w przybliżeniu różnicowalny w niektórych dzielnicach.
Przyjmę również jeszcze silniejszą postawę gładkości, gdy jest wystarczająco daleko. Załóżmy, że jest jakąś funkcją podliniową, taką jak (na przykład ), to pochodna ma nie zmienia się znacząco, gdy jest wystarczająco wolny. Intuicyjnie, gdy staje się większy, względny rozmiar sąsiedztwa zmniejsza się (ponieważ jego rozmiar to po prostu , który rośnie znacznie wolniej niż .) W końcu wielkość tego sąsiedztwa staje się tak nieznaczna (w stosunku do $n$ $\alpha(n)$ $n > \alpha(n)$ $n^c$ $T'(\xi \in (n - \alpha(n), n)$ $\alpha(n)$ $n$ $(n - \alpha(n), n)$ $\alpha(n)$ $n$ $n$ ), że szybkość zmiany w tym sąsiedztwie nie zmienia już tak radykalnie. $T(n)$

Teraz obie te właściwości są zakładane i nie mam pojęcia, jak się udowadniać w jakikolwiek rygorystyczny sposób. Ale jak powiedziałem wcześniej, trzymajmy kciuki i miejmy nadzieję na najlepsze.

Zacznijmy od relacji powtarzalności: Teraz założę, że jest wystarczająco gładki w przedziale między i . Odwoływanie się do jednego z naszych klasycznych narzędzi analitycznych, twierdzenia o wartości średniej, daje nam Ponadto, gdy jest wystarczająco duże, zakładamy, że jest w przybliżeniu takie samo w tym przedziale, a zatem przyjmuje również wartość dowolnej skończonej różnicy w tym przedziale. Oznacza to, że

\begin{aligned} T (n) & = T (n - n^{c}) + T (n^{c}) + f (n) \\ T (n) - T (n - n^{c}) & = T (n^{c}) + f (n) \\ n^{c} \frac{T (n) - T (n - n^{c})}{n^{c}} & = T (n^{c}) + f (n) \end{aligned}

$\begin{align*} T(n) &= T(n - n^c) + T(n^c) + f(n) \\ T(n) - T(n - n^c) &= T(n^c) + f(n) \\ n^c\frac{T(n) - T(n-n^c)}{n^c} &= T(n^c) + f(n) \end{align*}$

T

$T$

n - n^{c}

$n - n^c$

n

$n$

\frac{T (n) - T (n - n^{c})}{n^{c}} = T^{'} (ξ \in (n - n^{c}, n)) .

$\frac{T(n) - T(n-n^c)}{n^c} = T'(\xi \in (n - n^c, n)).$

n

$n$

T^{'} (ξ)

$T'(\xi)$

T^{'} (ξ) \approx \frac{T (n) - T (n - ϵ)}{ϵ} ϵ < n^{c}

$T'(\xi) \approx \frac{T(n) - T(n - \epsilon)}{\epsilon} ~~~~ \epsilon < n^c$ W szczególności weź aby uzyskać jeden -step aproksymacja podzielonej różnicy Możemy to teleskopować, aby uzyskać

ϵ = 1

$\epsilon = 1$

\begin{aligned} n^{c} (T (n) - T (n - 1)) & \approx T (n^{c}) + f (n) \\ T (n) - T (n - 1) & \approx \frac{T (n^{c}) + f (n)}{n^{c}} \end{aligned}

$\begin{align*} n^c (T(n) - T(n-1)) &\approx T(n^c) + f(n) \\ T(n) - T(n-1) &\approx \frac{T(n^c) + f(n)}{n^c} \\ \end{align*}$

T (n) \approx \sum_{k}^{n} \frac{T (k^{c})}{k^{c}} + \sum_{k}^{n} \frac{f (k)}{k^{c}}

$T(n) \approx \sum_k^n \frac{T(k^c)}{k^c} + \sum_k^n \frac{f(k)}{k^c}$

Perturbing ujawnia, że ma dwie fazy asymptotyczne, w zależności od asymptotycznej natury . $T(n)$ $T(n)$ $f(z)$

Gdy ( jest szybszy niż ), wówczas dominuje suma prawa, a my mamy które często można aproksymować całką . $f(n) = o(n^c)$ $f$ $n^c$ $T(n) = \Theta\left(\sum\limits_k^n \frac{f(k)}{k^c}\right)$ $\int\limits^n \frac{f(x)}{x^c} dx$

Kiedy , wówczas lewa suma dominuje po prawej stronie. Tutaj musimy przeanalizować sumę gdzie . $f(n) = \omega(n^c)$

(\sum_{k}^{n} \frac{T (k^{c})}{k^{c}}) + F_{c} (n)

$\left(\sum_k^n \frac{T(k^c)}{k^c}\right) + F_c(n)$

F_{c} (n) = \int^{n} \frac{f (x)}{x^{c}} d x

$F_c(n) = \int\limits^n \frac{f(x)}{x^c}dx$

Dzięki argumentowi gładkości możemy ponownie spojrzeć na to jako na zakotwiczoną w lewo sumę Riemanna, zbliżoną do całki . Zastosowanie podobnego twierdzenia o wartości średniej nad całką daje Możemy po prostu iść naprzód i przybliżyć to przez , co daje aproksymacja dla pewnej stałej która ogranicza szereg. $\int_n \frac{T(x^c)}{x^c} dx$

\sum_{k} \frac{T (k^{c})}{k^{c}} \approx \int^{n} \frac{f (x^{c})}{x^{c}} d x = n \frac{T (ξ < n^{c})}{ξ^{c}}

$\sum_k \frac{T(k^c)}{k^c} \approx \int^n \frac{f(x^c)}{x^c} dx = n\frac{T(\xi < n^c)}{\xi^c}$

n \frac{T (n^{c})}{n^{c}}

$n\frac{T(n^c)}{n^c}$

T (n) \leq n M \frac{T (n^{c})}{n^{c}} + F_{c} (n)

$\begin{equation} T(n) \le n M \frac{T(n^c)}{n^c} + F_c(n) \end{equation}$

M

$M$

Załóżmy teraz, że mamy iterowaną sekwencję gdzie , a następnie możemy użyć tej sekwencji do teleskopowania powyższej nierówności, aby uzyskać: Po raz kolejny możemy związać określenie za pośrednictwem stałej stwierdzić, że gdzie . Upraszczając trochę i łącząc niektóre terminy razem (w szczególności wiemy, że $(n, n^c, n^{c^2}, n^{c^3}, \dots, n^{c^k})$ $n^{c^k} < 2$

\begin{matrix} (*) & T (n) \leq n (\sum_{i}^{k - 1} \frac{M^{i}}{n^{c^{i}}} F_{c} (n^{c^{i}}) + \frac{M^{k}}{n^{c^{k}}}) \end{matrix}

$\label{eqn:meh} T(n) \le n \left(\sum_i^{k-1} \frac{M^i}{n^{c^i}}F_c(n^{c^i}) + \frac{M^k}{n^{c^k}}\right) \tag{*}$

F_{c} (n^{c^{i}})

$F_c(n^{c^i})$

T (n) = O (F_{c} (n) + n F_{c} (n^{c}) (M n^{- c} + M^{2} n^{- c^{2}} + \dots + M^{k} n^{- c^{k}}))

$T(n) = O\left(F_c(n) + n F_c(n^c) \left(M n^{-c} + M^2 n^{-c^2} + \dots + M^k n^{-c^k}\right)\right)$

k = \log_{c} (\frac{\log (2)}{\log (n)})

$k = \log_c\left(\frac{\log(2)}{\log(n)}\right)$

M n^{- c}

$Mn^{-c}$

n^{- c^{k}}

$n^{-c^k}$ jest stałą), otrzymujemy

T (n) = O (n k F_{c} (n) M^{k})

$T(n) = O\left(n k F_c(n) M^{k} \right)$

Jednak granica ta jest stosunkowo luźna i w miarę możliwości należy odwoływać się do . $(\ref{eqn:meh})$

Pamiętaj, że w żaden sposób nie jest to tak rygorystyczne. Nie zapewniłem żadnego wsparcia, że powinno to działać poza niektórymi nieporadnymi przybliżeniami. Niemniej jednak, jeśli potrzebujesz tylko szybkiego, asymptotycznego zgadywania ze względu na nieformalną analizę, możesz faktycznie zobaczyć, że ten schemat działa dobrze (dla wystarczająco dużych wartości , zwykle wystarcza w praktyce). $n$ $n > 10$

W każdym razie, dla wszystkich wyborów i , które próbowałem, następujące obliczenia gdzie wydaje się dawać dobre przybliżenia . Ta technika uogólnia także na powtarzające się formy które można aproksymować za pomocą gdzie $c$ $f$

\begin{aligned} \hat{T} (n) & = n \sum_{k}^{\log_{c} \log_{n} 2} \frac{M^{k}}{n^{c^{k}}} F (n^{c^{k}}) \\ F (n) & = \sum_{k}^{n} \frac{f (k)}{k^{c}} \end{aligned}

$\begin{align*} \hat T(n) &= n \sum_k^{\log_c \log_n 2} \frac{M^k}{n^{c^k}} F(n^{c^k}) \\ F(n) &= \sum_k^n \frac{f(k)}{k^c} \end{align*}$

M \approx \frac{\sum_{k} \frac{T (k^{c})}{k^{c}}}{n \frac{T (n^{c})}{n^{c}}}

$M \approx \frac{\sum_k \frac{T(k^c)}{k^c}}{n \frac{T(n^c)}{n^c}}$

T (n) = T (n - α (n)) + T (β (n)) + f (n)

$T(n) = T(n - \alpha(n)) + T(\beta(n)) + f(n)$

\begin{aligned} \hat{T} (n) & = n \sum_{k}^{#_{β} (n)} \frac{M^{k}}{α^{k} (n)} F (β^{k} (n)) \\ F (n) & = \sum_{k}^{n} \frac{f (k)}{α (k)} \end{aligned}

$\begin{align*} \hat T(n) &= n \sum_k^{\#_\beta(n)} \frac{M^k}{\alpha^k(n)} F(\beta^k(n)) \\ F(n) &= \sum_k^n \frac{f(k)}{\alpha(k)} \end{align*}$

α^{k} (n) = α (\overset{k}{\dots} (α (n)))

$\alpha^k(n) = \alpha(\stackrel{k}{\cdots}(\alpha(n)))$ a oznacza liczbę elementów sekwencji takie, że ostatni termin jest między a .

#_{β} (n)

$\#_\beta(n)$

n, β (n), β (β (n)), \dots, β^{#_{β} (n)} (n)

$n, \beta(n), \beta(\beta(n)), \dots, \beta^{\#_\beta(n)}(n)$

1

$1$

2

$2$

— Zawietrzny
źródło