Przykłady zaawansowanych algorytmów rekurencyjnych

Wyjaśniłem przyjacielowi słynny deterministyczny algorytm wyboru czasu liniowego (mediana algorytmu median).

Rekurencja w tym algorytmie (choć jest bardzo prosta) jest dość skomplikowana. Istnieją dwa wywołania rekurencyjne, każde o różnych parametrach.

Próbowałem znaleźć inne przykłady tak interesujących algorytmów rekurencyjnych, ale nie znalazłem żadnego. Wszystkie algorytmy rekurencyjne, które mogłem wymyślić, są albo prostymi rekurencjami ogona, albo prostym dzieleniem i podbijaniem (gdzie dwa wezwania są „takie same”).

Czy możesz podać kilka przykładów wyrafinowanej rekurencji?

Moja ulubiona rekurencja pojawia się w algorytmach wrażliwych na wyniki obliczania wypukłych kadłubów, najpierw przez Kirkpatrick i Seidel , ale później powtórzone przez innych. Niech oznacza czas obliczenia wypukłego kadłuba n punktów na płaszczyźnie, gdy wypukły kadłub ma h wierzchołków. (Wartość h nie jest z góry znana, poza trywialnym związanym h ≤ n .) Algorytm Kirkpatricka i Seidela daje powtarzalność T ( n , h ) = { O ( n ) $T(n,h)$$n$$h$$h$$h\le n$ przypadku gdzien1,n2≤3n/4orazn1+n2=norazh1+h2=h.

$$T(n,h) = \begin{cases} O(n) & \text{if }n \le 3 \text{ or } h \le 3 \\ T(n_1, h_1) + T(n_2, h_2) + O(n) & \text{otherwise} \end{cases}$$ $n_1, n_2 \le 3n/4$$n_1 + n_2 = n$$h_1 + h_2 = h$

Rozwiązaniem jest . Jest to trochę zaskakujące, ponieważ h nie jest równomiernym rozłożeniem parametru. Ale w rzeczywistości najgorszy przypadek ponownego wystąpienia ma miejsce, gdy h 1 i h 2 są około h / 2 ; jeśli w jakiś sposób magicznie h 1 jest zawsze stałe, rozwiązaniem byłoby T ( n , h ) = O ( n ) .$T(n,h) = O(n\log h)$$h$$h_1$$h_2$$h/2$$h_1$$T(n,h) = O(n)$

Użyłem wariantu tego nawrotu w jednym z moich pierwszych artykułów z topologii obliczeniowej : przypadku gdzie

$$T(n,g) = \begin{cases} O(n) & \text{if }n \le 3 \text{ or } g = 0\\ T(n_1, g_1) + T(n_2, g_2) + O(\min\{n_1, n_2\}) & \text{otherwise} \end{cases}$$ i g 1 + g 2 = $n_1 + n_2 = n$$g_1 + g_2 = g$ . Ponownie, rozwiązanie to i najgorszy przypadek występuje wtedy, gdy n i g są zawsze wyrównany.$O(n\log g)$$n$$g$

The recursion that I used in my paper "A linear-time algorithm for computing the Voronoi diagram of a convex polygon" by Aggarwal et al is also quite complicated.

Here is a description of the algorithm from our paper. In case it's not clear from the description, in step 3 the red points are partitioned into crimson and garnet points. Steps 1, 3, and 6 are all linear time. We also know that if $n$ is the total number of points, $|\mathrm{B}| \geq \alpha n$, $|\mathrm{R}| \geq \beta n$, and $|\mathrm{C}| \geq \gamma n$ for some $\alpha, \beta, \gamma > 0$.

I'll let you figure out why the entire algorithm takes linear time.

1. Partition the original points into the blue and red sets B and R.
2. Recursively compute the convex hull of the blue points.
3. Using the structure of the blue hull, select the crimson points C.
4. Add the crimson points to the blue hull one at a time.
5. Recursively compute the convex hull of the garnet points G.
6. Merge this garnet hull with the expanded blue hull of step 4.

What makes the algorithm linear is the ability to add a fixed fraction of the red points to the blue hull at constant cost per point. The points added are the crimson points.

The recursion is thus

$$T(n) = T(|B|) + T(|G|) + O(n)$$ where you don't know $|B|$ and $|G|$ but are guaranteed that $|B| + |G| \leq (1-\gamma) n$.

There is a variation on the median finding recurrence that comes from range searching with halfplanes. The recurrence itself is of the form

$$T(n) = T(n/2) + T(n/4) + cn$$ which is similar to the median-finding recurrence. For more on this, look at Jeff Erickson's lecture notes and in particular Section 4.

There are a bunch of cool recursive algorithms [1], [2] used in RNA secondary structure prediction. Left to its own devices, a strand of RNA will form base pairs with itself; one relatively simple example from [3] computes the maximum number of nested, paired bases an RNA string will form with itself:

$M(i,j)=\underset{i\leq k < j - L_{min}}{max} \begin{cases} M(i,k-1)+ M(k+1, j-1)+1 \\M(i, j-1) \end{cases}$

---

1. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information by M. Zuker, P. Stiegler (1981)

2. A Dynamic Programming Algorithm for RNA Structure Prediction Including Pseudoknots by E. Rivas, S. R. Eddy (1999)

3. Fast algorithm for predicting the secondary structure of single-stranded RNA by R. Nussinov, A. B. Jacobson (1980)

I still don't really understand what you mean by "sophisticated recursion". For example, the recursion step in the FFT algorithm is sophisticated!

But if you want to look for more complicated recursion, then mutual recursion might be one possible answer. Mutual recursion is useful when working with fuctional programming languages. Mutual recursion is the key feature of recursive descent parsers.

Z czubka mojej głowy, funkcja McCarthy 91

F(N) = 
    n - 100    if n > 100
    F(F(n+11)) if n <= 100

i funkcja Ackermanna

A(m, n) = 
    n + 1             if m = 0
    A(m-1, 1)         if m > 0 and n = 0
    A(m-1, A(m, n-1)) if m > 0 and n > 0

mogą być liczone jako niecodzienne, choć zabawkowe, rekurencyjne funkcje.