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

15

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?

if_zero_equals_one
źródło
2
Czy to zadanie domowe?
Bernard,
5
Nie, jest czas letni i lubię się uczyć. Wydaje mi się, że wyprzedzam, zamiast pozwolić mózgowi zamieniać się w papkę.
if_zero_equals_one
11
Okej, rozumiem. Do osób głosujących na migrację tego do przepełnienia stosu: jest to tutaj na temat, a nie na temat przepełnienia stosu. Programmers.SE jest przeznaczony do koncepcyjnych pytań na tablicy; Przepełnienie stosu służy do implementacji, pytań podczas kodowania.
3
Dzięki, dlatego właśnie to tutaj zrobiłem. Poza tym lepiej wiedzieć, jak łowić ryby niż otrzymywać ryby.
if_zero_equals_one
1
W tym szczególnym przypadku jest to na ogół nieskończona rekurencja, ponieważ b (a (0)) wywołuje nieskończenie wiele innych terminów b (a (0)). Byłoby inaczej, gdyby była to formuła matematyczna. Gdyby Twoja konfiguracja była inna, działałoby inaczej. Podobnie jak w matematyce, w cs niektóre problemy mają rozwiązanie, niektóre nie, niektóre mają łatwe, inne nie. Istnieje wiele wzajemnie rekurencyjnych przypadków, w których istnieje rozwiązanie. Czasami, aby nie wysadzić stosu, trzeba użyć wzoru trampoliny.
Job

Odpowiedzi:

11

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.

btilly
źródło
5

Ś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 .

jimreed
źródło
Nie szukam tutaj konkretnych funkcji. Szukam ogólnego sposobu znalezienia czasu działania funkcji rekurencyjnych, które się nawzajem wywołują.
if_zero_equals_one
1
Nie jestem pewien, czy istnieje rozwiązanie w ogólnym przypadku. Aby Big-O miał sens, musisz wiedzieć, czy algorytm kiedykolwiek się zatrzyma. Istnieje kilka algorytmów rekurencyjnych, w których musisz uruchomić obliczenia, zanim dowiesz się, jak długo to potrwa (np. Ustalenie, czy punkt należy do zestawu Mandlebrota, czy nie).
jimreed,
Nie zawsze adzwoni tylko bwtedy, gdy przekazany numer wynosi> = 0. Ale tak, istnieje nieskończona pętla.
btilly,
1
@btilly przykład został zmieniony po opublikowaniu mojej odpowiedzi.
jimreed,
1
@jimreed: I to znowu zostało zmienione. Usunąłbym mój komentarz, gdybym mógł.
btilly,
4

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.

Gilles „SO- przestań być zły”
źródło
1

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.

Praca
źródło
0

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.

davidk01
źródło
-5

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

Zaraz
źródło
2
Wydajność Big-O określa się, przyjmując najwyższą kolejność dowolnej wywoływanej metody i mnożąc ją przez kolejność metody wywołującej. Jednak gdy zaczniesz mówić o wydajności wykładniczej i czynnikowej, możesz zignorować wydajność wielomianową. Uważam , że to samo dotyczy porównania wykładniczego i czynnikowego: wygrane czynnikowe. Nigdy nie miałem do analizy systemu, który był zarówno wykładniczy i silni.
Anon,
5
To jest niepoprawne. Rekurencyjnej formy obliczania n-tą liczbę Fibonacciego i quicksort są O(2^n)i O(n*log(n)), odpowiednio.
niepythonic
1
Nie robiąc jakiegoś fantazyjnego dowodu, chciałbym skierować cię na stronę amazon.com/Introduction-Algorytmy-Drugi-Tomoma-Cormen/dp/... i spróbuj zajrzeć na tę stronę SE cstheory.stackexchange.com .
Bryan Harrington,
4
Dlaczego ludzie głosowali na tę okropnie złą odpowiedź? Wywołanie metody zajmuje czas proporcjonalny do czasu, jaki zajmuje ta metoda. W tym przypadku awywołania metod bi bwywołania, awięc nie można po prostu założyć, że żadna metoda wymaga czasu O(1).
btilly,
2
@Anon - Plakat żądał arbitralnie podwójnej rekurencyjnej funkcji, a nie tylko tej pokazanej powyżej. Podałem dwa przykłady prostej rekurencji, które nie pasują do twojego wyjaśnienia. Trywialne jest przekształcanie starych standardów w formę „podwójnie rekurencyjną”, taką, która była wykładnicza (odpowiadająca twojemu zastrzeżeniu) i która nie była (nie objęta).
niepythonic