Nitr0Skay Temat założony przez niniejszego użytkownika |
Iteracja vs Rekurencja - złożoność obliczeniowa/pamięciowa » 2015-06-13 14:45:37 Witam. Zastanawiam się, jak obliczyć i porównać złożoność obliczeniową Iteracji i Rekurencji dla danego działania/programu. Słyszałem kiedyś, że Rekurencja posiada znacznie większą złożoność obliczeniową (około 2, lub trzy krotną). Zastanawia mnie, jak to pokazać oraz udowodnić. Dla liczenia silni raczej za bardzo się to nie różni. Zademonstruję: Iteracja #include <iostream>
using namespace std;
int main()
{
int silnia = 1, n = 0;
cout << "Jest to program obliczajacy silnie metoda iteracyjna" << endl;
cout << "Podaj liczbe, ktorej silnie pragniesz obliczyc: ";
cin >> n;
if( n <= 1 )
{
cout << "Silnia wynosi jeden (1)" << endl;
}
else
{
cout << endl << "Silnia z liczby " << n << " wynosi:" << endl;
cout << n << "! = ";
for( int i = 1; i <= n; i++ )
{
cout << i << " ";
silnia *= i;
if( i != n )
cout << "* ";
}
cout << " = " << silnia << endl;
}
return 0;
}
Rekurencja #include <iostream>
using namespace std;
int liczSilnie( int n )
{
if( n <= 1 )
return 1;
return( n * liczSilnie( n - 1 ) );
}
int main()
{
int silnia = 1, n = 0;
cout << "Jest to program obliczajacy silnie metoda rekurencyjna" << endl;
cout << "Podaj liczbe, ktorej silnie chcesz obliczyc: ";
cin >> n;
cout << "Silnia liczby " << n << " wynosi: " << liczSilnie( n ) << endl;
return 0;
}
Zatem sami widzicie, że ilość operacji w obu tych przypadkach jest mniej więcej podobna. W iteracji jest jedno porównanie i jedna operacja, natomiast w rekurencji jest jedno porównanie i też jedna operacja (albo wywołanie tej samej funkcji, nie wiem, czy można to tak nazwać). Jak zatem na tym przykładzie udowodnić, że Iteracja jest sprawniejsza i wydajniejsza, oraz posiada ona mniejszą złożoność obliczeniową ?? Ja nie mam kompletnie koncepcji, zatem proszę o drobną pomoc lub nakierowanie. Z góry bardzo dziękuję. A tak z innej beczki, jakie jeszcze wady i zalety (o których mogę nie wiedzieć) zarówno rekurencja, jak i iteracja ? Jakie mają podobieństwa i różnice ? Z góry dziękuję. |
|
pekfos |
» 2015-06-13 15:17:50 |
|
Nitr0Skay Temat założony przez niniejszego użytkownika |
» 2015-06-13 17:38:59 Dlaczego niby bzdura ? Moglby pan to wyjasnic, lub nakierowac na jakies zrodlo ?? |
|
pekfos |
» 2015-06-13 19:07:04 Bo to porównywanie ze sobą dwóch technik, które nie służą do tego samego. Co to w ogóle jest 'złożoność obliczeniowa rekurencji', czy iteracji..? Jedno i drugie to skok we wskazane miejsce, więc o jakiej niby złożoności obliczeniowej chcesz tu mówić..? Technika programowania nie ma złożoności obliczeniowej, ma ją algorytm, a, w zależności od wybranej techniki, łatwiej bądź trudniej tą złożoność spieprzyć. Przykład masz w temacie, który podałem - iteracyjny algorytm w czasie liniowym i rekurencyjny w wykładniczym, oba robiące to samo. | lub nakierowac na jakies zrodlo ?? |
Nie znam, wystarczy myśleć i wiedzieć cokolwiek o temacie, o który się pyta. Lub użyć wyszukiwarki.. |
|
Nitr0Skay Temat założony przez niniejszego użytkownika |
» 2015-06-14 10:58:43 Dobra, juz mam odpowiedz. Chodzilo raczej o zlozonosc pamieciowa. Rekurencja jakby przy kazdym wywolaniu funkcji rezerwuje sobie pamiec, przez co jest ona tak malo wydajna dla wielszych ilosci danych. |
|
DejaVu |
» 2015-06-14 11:55:40 Rekurencja jakby przy kazdym wywolaniu funkcji rezerwuje sobie pamiec, przez co jest ona tak malo wydajna dla wielszych ilosci danych.
|
Kolejna bzdura. Skąd Ty czerpiesz te informacje? Każde wywołanie funkcji potrzebuje tyle bajtów pamięci ile zajmują zmienne przekazane poprzez argumenty do funkcji. Wywołania funkcji odbywają się na PAMIĘCI STOSU, a pamięć stosu jest bardzo szybka, więc operacje wywołań funkcji są bardzo wydajne i tym samym rekurencja jest również bardzo wydajna. Przeciętny algorytm rekurencyjny zazwyczaj jest szybszy niż algorytm równoważny, zaimplementowany na jakimś kontenerze, pełniącym rolę stosu. /edit: Przeczytaj sobie tematy: http://cpp0x.pl/forum/temat/?id=19695&p=2http://cpp0x.pl/forum/temat/?id=12372http://cpp0x.pl/forum/temat/?id=11756 |
|
Nitr0Skay Temat założony przez niniejszego użytkownika |
» 2015-06-14 12:18:20 Dziekuje, w wolnej chwili poczytam :) |
|
| « 1 » |