[C++] Przekroczono limit czasu

pytanie zadane 23 października 2016 w C i C++ przez Elenek Nowicjusz (160 p.)

Witam robię kurs Mirosława Zelanta i wykonując zadanie domowe natknąłem się na pewien problem dotyczący programu. Kompiluje się on poprawnie jednak u mnie działa on bez końca a w kompilatorze www wyświetla się błąd odnośnie przekroczony limit czasu. Macie może jakieś sugestie na ten temat?

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;
//oblicz czas jaki wykonuje się algorytm rekurencyjnie a jak iteracyjnie

int fib( int n )
{
    if( n == 1 || n == 2 ) return 1;
    else return fib( n - 1 ) + fib( n - 2 );
    
}

int main()
{
    clock_t start, stop;
    double czas;
    
    start = clock();
    fib( 1000 );
    stop = clock();
    
    czas =( double )( stop - start ) / CLOCKS_PER_SEC;
    cout << "Czas algorytmu wykonywanego rekurencyjnie: " << czas << endl;
    
    long double fib[ 1000 ]; int n = 1000;
    
    start = clock();
    fib[ 0 ] = 1;
    fib[ 1 ] = 1;
    
    for( int i = 2; i < n; i++ )
    {
        fib[ i ] = fib[ i - 1 ] + fib[ i - 2 ];
    }
    stop = clock();
    czas =( double )( stop - start ) / CLOCKS_PER_SEC;
    cout << "Czas algorytmu wykonywanego iteracyjnie: " << czas;
    
    return 0;
}

2 odpowiedzi

odpowiedź 23 października 2016 przez niezalogowany

Prosta sprawa, wybrałeś za duże N dla fibonacciego. Pracujesz na int'ach, więc max value to:

2147483647

A poprawny wynik dla n=1000 to:

434665576869374564356885276750 406258025646605173717804024817 290895365554179490518904038798 400792551692959225930803226347 752096896232398733224711616429 964409065331879382989696499285 16003704476137795166849228875

Czyli mamy tutaj do czynienia ze znacznym overflow'em ;)

komentarz 23 października 2016 przez criss Mędrzec (172,590 p.)

Poza tym ze względu na rekurencje stack overflow i tak wystąpi przy tylu wywołaniach funkcji. Już nie mówiąc o czasie wykonywania. Już dla fib(10) mamy kilkadziesiąt wywołań...

komentarz 23 października 2016 przez niezalogowany

@Criss Raczej nie, chyba że masz bardzo mało pamięci

komentarz 23 października 2016 przez criss Mędrzec (172,590 p.)

Spróbuj policzyć ile będzie wywołań dla fib(1000) i pomnóż to przez 4 (Bajty) :P Oczywiście to będzie więcej bo punkt powrotu to też pamięć. Już przy fib(40) liczba wywołań to 204668309...

komentarz 23 października 2016 przez adrian17 Ekspert (344,860 p.)

Spróbuj policzyć ile będzie wywołań dla fib(1000) i pomnóż to przez 4 (Bajty) :P

Zajęcie pamięci stosu zależy nie od liczby wywołań, tylko od głębokości rekurencji - która będzie rzędu... 1000.

komentarz 23 października 2016 przez criss Mędrzec (172,590 p.)

Mógłbyś wytłumaczyć dlaczego, bo nie rozumiem?

komentarz 23 października 2016 przez adrian17 Ekspert (344,860 p.)

https://en.wikipedia.org/wiki/Call_stack

Stos (w kontekście danych programu, a nie struktury danych) przechowuje głównie zmienne lokalne, argumenty funkcji oraz dane potrzebne przy wychodzeniu z funkcji. Przy wywoływaniu funkcji dane są rezerwowane/pushowane na stos, przy wychodzeniu z funkcji są pop'owane.

Jeśli zrobisz

void f(){}
int main(){
    f();
    f();
    f();
}

Wywołując f() za każdym razem rezerwujesz, po czym zdejmujesz N bajtów ze stosu. Niezależnie ile razy wywołasz f(), zużycie pamięci na stosie będzie wynosiło zaledwie N.

W tym przypadku:

void f() {
    f();
}

(pomijając optymalizacje kompilatora takie jak TCO) f() będzie wchodziło coraz "głębiej", z każdym wywołaniem biorąc kolejne N bajtów ze stosu, aż w końcu miejsce się skończy.

Innymi słowy - "stack overflow" w rekurencji zależy od głębokości wywołań, nie od samj ich ilości. Ilość wywołań po prostu wpływa na czas wykonania.