Biorąc pod uwagę dowolną funkcję podwójnie rekurencyjną, jak obliczyć jej czas działania?
Na przykład (w pseudokodzie):
int a(int x){
if (x < = 0)
return 1010;
else
return b(x-1) + a(x-1);
}
int b(int y){
if (y <= -5)
return -2;
else
return b(a(y-1));
}
Lub coś podobnego.
Jakich metod można lub należy użyć, aby określić coś takiego?
Odpowiedzi:
Zmieniasz swoją funkcję. Ale wybieraj te, które będą działać wiecznie bez konwersji.
Rekurencja szybko się komplikuje. Pierwszym krokiem do analizy proponowanej podwójnie rekurencyjnej funkcji jest próba prześledzenia jej na niektórych przykładowych wartościach, aby zobaczyć, co ona robi. Jeśli twoje obliczenia przechodzą w nieskończoną pętlę, funkcja nie jest dobrze zdefiniowana. Jeśli twoje obliczenia przechodzą w spiralę, która ciągle się powiększa (co dzieje się bardzo łatwo), prawdopodobnie nie jest dobrze zdefiniowana.
Jeśli prześledzenie go daje odpowiedź, wówczas próbujesz znaleźć jakiś wzorzec lub relację między odpowiedziami. Gdy to zrobisz, możesz spróbować dowiedzieć się, jaki jest czas jego działania. Wyjaśnienie tego może być bardzo, bardzo skomplikowane, ale mamy wyniki takie jak twierdzenie Master, które pozwala nam znaleźć odpowiedź w wielu przypadkach.
Uważaj, że nawet przy pojedynczej rekurencji łatwo jest wymyślić funkcje, których czasu działania nie wiemy, jak obliczyć. Rozważ na przykład:
To jest obecnie nieznany , czy ta funkcja jest zawsze dobrze zdefiniowane, nie mówiąc już, co jest jego czas pracy.
źródło
Środowisko wykonawcze tej konkretnej pary funkcji jest nieskończone, ponieważ żadna z nich nie powraca bez wywołania drugiej. Wartość zwracana
a
jest zawsze zależny od wartości zwracanej przez wywołanieb
który zawsze wywołujea
... i to co jest znane jako nieskończonej rekurencji .źródło
a
dzwoni tylkob
wtedy, gdy przekazany numer wynosi> = 0. Ale tak, istnieje nieskończona pętla.Oczywistą metodą jest uruchomienie funkcji i zmierzenie czasu jej trwania. To tylko mówi ci, ile czasu zajmuje dane wejście. A jeśli nie wiesz wcześniej, że funkcja się kończy, trudne: nie ma mechanicznego sposobu, aby dowiedzieć się, czy funkcja się kończy - to jest problem zatrzymania i jest nierozstrzygalny.
Znalezienie czasu działania funkcji jest podobnie nierozstrzygalne, zgodnie z twierdzeniem Rice'a . W rzeczywistości twierdzenie Rice'a pokazuje, że nawet podjęcie decyzji, czy funkcja działa w
O(f(n))
czasie, jest nierozstrzygalne.Więc najlepiej, co możesz zrobić ogólnie, to użyć swojej ludzkiej inteligencji (która, o ile wiemy, nie jest ograniczona przez granice maszyn Turinga) i spróbować rozpoznać wzór lub wymyślić jeden. Typowym sposobem analizy czasu działania funkcji jest przekształcenie definicji rekurencyjnej funkcji w równanie rekurencyjne w czasie jego działania (lub zbiór równań dla funkcji wzajemnie rekurencyjnych):
Co następne? Masz teraz problem matematyczny: musisz rozwiązać te równania funkcjonalne. Podejście, które często działa to, aby włączyć te równania na temat funkcji całkowitych w równaniach na funkcji analitycznych i używać rachunku do rozwiązania tych interpretacji funkcji
T_a
iT_b
jako funkcji generujących .Przy generowaniu funkcji i innych dyskretnych zagadnień matematycznych polecam książkę Concrete Mathematics autorstwa Ronalda Grahama, Donalda Knutha i Orena Patashnika.
źródło
Jak zauważyli inni, analiza rekurencji może być bardzo trudna bardzo szybko. Oto inny przykład takiej rzeczy: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences ciężko jest obliczyć odpowiedź i czas ich trwania. Wynika to z faktu, że te wzajemnie rekurencyjne funkcje mają „trudną formę”.
W każdym razie spójrzmy na ten prosty przykład:
http://pramode.net/clojure/2010/05/08/clojure-trampoline/
Zacznijmy od próby obliczenia
funa(m), m > 0
:Czas działania wynosi:
Teraz wybierzmy inny, nieco bardziej skomplikowany przykład:
Zainspirowany http://planetmath.org/encyclopedia/MutualRecursion.html , który sam w sobie jest dobrym odczytem, spójrzmy na: „” „Liczby Fibonacciego można interpretować poprzez wzajemną rekurencję: F (0) = 1 i G (0 ) = 1, przy czym F (n + 1) = F (n) + G (n) i G (n + 1) = F (n). "" "
Więc jaki jest czas działania F? Pójdziemy w drugą stronę.
Cóż, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Teraz R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Nietrudno zauważyć, że R (F (m)) = F (m) - np. Liczba wywołań funkcji potrzebnych do obliczenia liczby Fibonacciego o indeksie i jest równa wartości liczby Fibonacciego o indeksie i. Zakładało to, że dodanie dwóch liczb razem jest znacznie szybsze niż wywołanie funkcji. Gdyby tak nie było, byłoby to prawdą: R (F (1)) = R (F (0)) + 1 + R (G (0)), a analiza tego byłaby bardziej skomplikowana, ewentualnie bez łatwego rozwiązania w formie zamkniętej.
Zamknięta postać sekwencji Fibonacciego niekoniecznie jest łatwa do odkrycia, nie wspominając o bardziej skomplikowanych przykładach.
źródło
Pierwszą rzeczą do zrobienia jest pokazanie, że funkcje, które zdefiniowałeś, kończą się i dla których dokładnie wartości. W zdefiniowanym przykładzie
b
wygasa tylkoy <= -5
dlatego, że jeśli podasz jakąkolwiek inną wartość, będziesz miał termin formularzab(a(y-1))
. Jeśli zrobisz trochę więcej rozszerzania, zobaczysz, że termin formyb(a(y-1))
ostatecznie prowadzi do terminu,b(1010)
który prowadzi do terminu,b(a(1009))
który ponownie prowadzi do tego terminub(1010)
. Oznacza to, że nie możesz podłączyć żadnej wartościa
, która nie spełnia wymagań,x <= -4
ponieważ w rezultacie powstanie nieskończona pętla, w której wartość do obliczenia zależy od wartości do obliczenia. Zasadniczo ten przykład ma stały czas działania.Prosta odpowiedź brzmi więc, że nie ma ogólnej metody określania czasu działania funkcji rekurencyjnych, ponieważ nie ma ogólnej procedury, która określa, czy funkcja zdefiniowana rekurencyjnie kończy działanie.
źródło
Runtime jak w Big-O?
To proste: O (N) - zakładając, że istnieje warunek zakończenia.
Rekurencja jest po prostu zapętlaniem, a prosta pętla to O (N) bez względu na to, ile rzeczy robisz w tej pętli (a wywoływanie innej metody jest tylko kolejnym krokiem w pętli).
Ciekawie byłoby, gdybyś miał pętlę w ramach jednej lub więcej metod rekurencyjnych. W takim przypadku uzyskasz jakąś wykładniczą wydajność (pomnożenie przez O (N) przy każdym przejściu przez metodę).
źródło
O(2^n)
iO(n*log(n))
, odpowiednio.a
wywołania metodb
ib
wywołania,a
więc nie można po prostu założyć, że żadna metoda wymaga czasuO(1)
.