algorytmy rekurencyjne
Ostatnio zmodyfikowano 2014-08-19 17:29
ison |
» 2011-01-26 18:51:55 @DejaVu chodzi Ci o moją implementację Fibonacciego? To był najgorszy sposób liczenia Fibonacciego jaki istnieje, chodziło tylko aby pokazać jak to wyliczyć rekurencyjnie.
Dla liczby n wywołań nie będzie n ani n*2
dla n=3 będzie to wyglądało w ten sposób:
fib
/ \
fib fib
/ \ / \
fib fib fib fib
co rośnie w bardzo szybkim tempie |
|
DejaVu |
» 2011-01-26 18:55:59 I myślisz, że fibonaci iteracyjny nie wykona takich obliczeń... zaimplementuj jeden i drugi algorytm to będzie można dyskutować. |
|
Elaine |
» 2011-01-26 19:02:12 Porównujesz rekurencję z rekurencją (w tym drugim przypadku z jawnym stosem). Cool.
Może jednak przeczytaj jego posty, co?
| wg. mojej zdroworozsądkowej analizy dla prostych algorytmów matematycznych (to znaczy obliczania n-tego wyrazu nierozbudowanego ciągu) pętla for ma mniejsze zużycie zasobów pamięcio-czasowych niż rekurencja? |
| Ja tylko dyskutuję z manierą stosowania rekurencji do silni, ciągów Fibbonachiego i innych ciągów, do których zrobienie pętli jest "skomplikowane". |
Z tego jasno wynika, iż jsc twierdzi, że rekurencja to zło... jeśli istnieje algorytm robiący to samo iteracyjnie. Czyli jak chcesz porównywać rekurencyjną i iteracyjną implementację jakiegoś sortowania, to weź algorytm, który nie wymaga rekurencji.
Swoją drogą - jeśli rekurencja jest taka dobra, to dlaczego kompilatory starają się optymalizować rekurencję ogonową do postaci pętli? ;>
EDIT (wygląda na to, że trochę się spóżniłem :>)
| I myślisz, że fibonaci iteracyjny nie wykona takich obliczeń... zaimplementuj jeden i drugi algorytm to będzie można dyskutować. |
To jest jedna prosta pętla. W jaki niby sposób miałaby osiągnąć złożoność O(2^n)? |
|
ison |
» 2011-01-26 19:09:10 I myślisz, że fibonaci iteracyjny nie wykona takich obliczeń... zaimplementuj jeden i drugi algorytm to będzie można dyskutować.
|
złożoność programu nie jest trudno wyliczyć :) różnica jest ogromna między fibonaccim iteracyjnym i rekurencyjnym |
|
ThudPoland |
» 2011-01-26 19:11:54 Jak będzie mi się chciało to napiszę rekurencyjnie i iteracyjnie program rozwiązujący dla dowolnej liczby problem Collatza i podam wyniki. |
|
Elaine |
» 2011-01-26 19:12:10 Chciałeś, to masz: #include <ctime>
#include <cstdio>
using namespace std;
unsigned fibr( unsigned x )
{
if( x == 0 ) return 0;
if( x == 1 ) return 1;
return fibr( x - 1 ) + fibr( x - 2 );
}
unsigned fibi( unsigned x )
{
if( x == 0 ) return 0;
if( x == 1 ) return 1;
unsigned n1 = 0, n2 = 1, temp = 1;
for( unsigned n = 2; n <= x; ++n )
{
temp = n1 + n2;
n1 = n2;
n2 = temp;
}
return n2;
}
void test( unsigned( * fn )( unsigned ) )
{
clock_t start = clock();
volatile unsigned result = fn( 40 );
printf( "%ldms\n", static_cast < long >( clock() - start ) * CLOCKS_PER_SEC / 1000 );
}
int main()
{
test( fibr );
test( fibi );
}
Output (MSVC 2010, Release): 1212ms
0ms |
|
ThudPoland |
» 2011-01-26 19:12:12 <<double>> |
|
DejaVu |
» 2011-01-26 19:30:09 Te algorytmy nie są równoważne - wynik dają ten sam i owszem. To tak jak bym porównał quicksorta do sortowania bąbelkowego - efekt ten sam, a różny sposób dojścia do rozwiązania. |
|
| 1 2 « 3 » 4 5 6 |