Big O metod rekursywnych

Question

Mam trudności z określeniem dużych O prostych metod rekursywnych. Nie mogę objąć głowy tym, co się dzieje, gdy metoda nazywa się wiele razy. Byłbym bardziej konkretny na temat moich obszarów zamieszania, ale w tej chwili próbuję odpowiedzieć na kilka pytań i zamiast nie chcieć oszukiwać, proszę, aby każdy, kto odpowiedział na to pytanie, wymyślił prostą metodę rekurencyjną i dostarczyć prostego wyjaśnienia dużej O wspomnianej metody. (Najlepiej w Javie ... języku, którego się uczę.)

Dziękuję.

Answer 1

Możesz również zdefiniować kolejność rekursywnie. Na przykład załóżmy, że masz funkcję f. Aby obliczyć f (n) wykonuje k kroków. Teraz chcesz obliczyć f (n + 1). Powiedzmy, że f (n + 1) wywołuje f (n) raz, a następnie f (n + 1) przyjmuje k + kilka stałych kroków. Każde wywołanie wymaga dodatkowych stałych kroków, więc ta metoda jest O (n).

Teraz spójrz na inny przykład. Powiedzmy, że wdrożenie Fibonacciego naiwnie przez dodanie dwóch poprzednich wyników:

fib(n) = { return fib(n-1) + fib(n-2) } 

Teraz powiedzmy, że można obliczyć fib (n-2) oraz fib (n-1) zarówno o stopniach K. Aby obliczyć fib (n), potrzebujesz kroków k + k = 2 * k. Teraz powiedzmy, że chcesz obliczyć fib (n + 1). Potrzebujesz więc dwa razy więcej kroków niż w przypadku fib (n-1). Więc wydaje się, że to O (2^N)

To nie jest zbyt formalne, ale miejmy nadzieję, że w ten sposób można się trochę poczuć.

Answer 2

Możesz odwołać się do twierdzenia głównego o znalezieniu dużego O metod rekursywnych. Oto artykuł wikipedia: http://en.wikipedia.org/wiki/Master_theorem

Chcesz myśleć o rekurencyjnym problemie, takim jak drzewo. Następnie rozważ każdy poziom drzewa i ilość wymaganej pracy. Problemy z reguły mieszczą się w 3 kategoriach: root ciężki (pierwsza iteracja >> reszta drzewa), zrównoważony (każdy poziom ma równe ilości pracy), liść ciężki (ostatnia iteracja >> reszta drzewa).

Przeprowadzanie scalania sortowania jako przykład:

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

Można zobaczyć, że każde wezwanie mergesort z kolei wywołuje 2 więcej mergeSorts 1/2 pierwotnej długości. Wiemy, że procedura scalania będzie wymagała czasu proporcjonalnego do liczby scalanych wartości.

Relacja rekurencyjna to wtedy T (n) = 2 * T (n/2) + O (n). Te dwa elementy pochodzą z 2 połączeń, a n/2 pochodzi z każdego połączenia mającego tylko połowę liczby elementów. Jednak na każdym poziomie znajduje się ta sama liczba elementów, które muszą zostać połączone, więc stała praca na każdym poziomie to O (n).

Wiemy, że praca jest równomiernie rozłożona (O (n) na każdej głębokości), a drzewo jest log_2 (n) głębokie, więc dużym O funkcji rekursywnej jest O (n * log (n)).