Jak określić czas działania podwójnej funkcji rekurencyjnej?

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?

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:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

To jest obecnie nieznany , czy ta funkcja jest zawsze dobrze zdefiniowane, nie mówiąc już, co jest jego czas pracy.

Środowisko wykonawcze tej konkretnej pary funkcji jest nieskończone, ponieważ żadna z nich nie powraca bez wywołania drugiej. Wartość zwracana ajest zawsze zależny od wartości zwracanej przez wywołanie bktóry zawsze wywołuje a... i to co jest znane jako nieskończonej rekurencji .

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):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

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_ai T_bjako funkcji generujących .

Przy generowaniu funkcji i innych dyskretnych zagadnień matematycznych polecam książkę Concrete Mathematics autorstwa Ronalda Grahama, Donalda Knutha i Orena Patashnika.

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/

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Zacznijmy od próby obliczenia funa(m), m > 0:

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

Czas działania wynosi:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

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.

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

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));
}

bwygasa tylko y <= -5dlatego, że jeśli podasz jakąkolwiek inną wartość, będziesz miał termin formularza b(a(y-1)). Jeśli zrobisz trochę więcej rozszerzania, zobaczysz, że termin formy b(a(y-1))ostatecznie prowadzi do terminu, b(1010)który prowadzi do terminu, b(a(1009))który ponownie prowadzi do tego terminu b(1010). Oznacza to, że nie możesz podłączyć żadnej wartości a, która nie spełnia wymagań, x <= -4ponieważ 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.

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ę).