Złożoność i funkcje rekurencyjne

> LeekScript samouczek

Ostrzeżenie: ten artykuł jest matematycznie intensywny (przynajmniej dla tej wiki). Nie stosować bez porady lekarskiej.

A poważniej: tutaj spróbuję porozmawiać o Optymalizacji funkcji rekurencyjnych (The_Recursion). Ten artykuł jest bardziej przeznaczony dla osób zainteresowanych programowaniem funkcyjnym i teorią programowania.

Podczas pisania funkcji rekurencyjnej nie zawsze łatwo jest wiedzieć, ile wywołań wykonamy, zanim dojdziemy do wyniku. Lub nawet jeśli dojdziemy do wyniku, czasami. Samouczek na La_Récursivité daje sposoby optymalizacji funkcji rekurencyjnych, ale nie bada złożoności ani korekcji; Dlatego zilustruję tutaj przykładami niektóre metody, aby się odnaleźć.

Ta lista przykładów nie jest wyczerpująca, każdy z twoich algorytmów będzie musiał dokładnie zbadać przeprowadzone operacje.

Następnie do ciebie należy skopiowanie tych pomysłów do swoich osobistych algorytmów, a jeśli znajdziesz inne przykłady warte wspomnienia, wyjaśnij je tutaj!

Pierwsze przykłady

Niektóre proste funkcje rekurencyjne mają łatwą do zbadania złożoność. Tak jest w przypadku pierwszego przykładu samouczka dotyczącego rekurencji:

funkcja sumaN(n) { jeśli (n === 0) { zwróć 0; } else { return n + sumaN(n - 1); } }

Tutaj sprawa jest dość prosta: łatwo zauważyć, że jeśli podamy tej funkcji liczbę całkowitą n (dodatnią!), to doda ona n do sumy od 0 do n-1, którą oblicza nazywając siebie parzystą. Więc zrobimy n + (n-1 + ... + (0)...), co daje n dodawania i n wywołań funkcji, czyli złożoność O( n).

Jeśli jednak jako dane wejściowe podamy ujemną liczbę całkowitą, ta funkcja spowoduje przepełnienie stosu: doda liczby ujemne, nigdy nie osiągając 0. Podobnie, jeśli podamy liczbę niecałkowitą, nigdy nie osiągniemy 0, odejmując kilka razy 1 . Zwróć więc uwagę na „poprawkę” swoich funkcji rekurencyjnych: jeśli nie przewidziałeś wszystkich przypadków lub używasz ich z danymi wejściowymi, które nie odpowiadają temu, co miałeś na myśli podczas ich kodowania, możesz mieć nieprzyjemne niespodzianki.

Samouczek dotyczący optymalizacji zawiera przykład funkcji złożoności O(2^n):

funkcja getAllCombos(list_items){ var nb_items = count(list_items);

if(nb_items == 1) { zwróć [[], elementy_listy]; }

var sub_list = subArray(list_items, 1, nb_items - 1); var częściowa_lista_kombinacji = getAllCombos(lista_podrzędnych); // Wywołanie rekurencyjne var m = count(list_combos_partial);

//Następnie duplikujemy listę kombinacji: zachowujemy te, które mieliśmy i dodajemy te same z pierwszym elementem liste_items for(var i=0; i P(n) = 2*P(n-1). Ponieważ mamy również P(1) = 2, otrzymujemy wzór P(n) = 2 * ... * 2 = 2^n, stąd (w najmniej) złożoność wykładnicza. Możemy wtedy pokazać, że ta funkcja ma złożoność wykładniczą (i nie większą): każde wywołanie funkcji tworzy tablicę o rozmiarze n-1 z subArray (cost: O(n)), wtedy m wypycha z m rozmiar częściowej tablicy kombi, tj. 2^(n-1) (cost: K * 2^(n-1) z K naciśnięciem cost), co obniża koszt podtablicy, a tym samym prowadzi do złożoności określonej przez liczbę P(n) wykonanych wypchnięć.

To jest ten pomysł, który rozwinę tutaj: uzyskaj formułę rekurencyjną i spróbuj wydedukować formułę zwiększającą liczbę wywołań, aby ostatecznie wydedukować złożoność, badając, co robi funkcja oprócz wywołań rekurencyjnych. Nie będę już tak dużo mówić o korekcie (z wyjątkiem samego końca), ale miej to na uwadze…

W dalszej części C(n) będzie oznaczać koszt badanej funkcji.

Proste powtórzenia: C(n) = f(C(n-1))

Słowo „prosty” nie oznacza tu kompleksów