Problem z odmierzaniem czasu

Question

Witam. Muszę policzyć czas w jakim program oblicza n-ty wyraz ciągu Fibonacciego sposobem rekurencyjnym i iteracyjnym. Problem polega na tym, że nie ważne który to wyraz ciągu, iteracyjnie czas zawsze pokazuje 0. Rekurencyjnie nie ma tego problemu.

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iomanip>
using namespace std;
long long iteracyjnie(int n) {
    
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else if (n > 1) {
        long long fib0 = 0;
        long long fib1 = 1;
        long long fibn = 0;
        for (int i = 2; i <= n; i++) {
             fibn = fib0 + fib1;
            fib0 = fib1;
            fib1 = fibn;
        }
        return fibn;
    }
}
long long rekurencyjnie(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else if (n > 1) {
        return rekurencyjnie(n - 1) + rekurencyjnie(n - 2);
    }
}
int main()
{
    int n = 0;
    cout << "Podaj n: ";
    cin >> n;
    clock_t start, end;
    double czas_obl;
    start = clock();
    iteracyjnie(n);
    end = clock();
    czas_obl = 1.0 * (end - start) / CLK_TCK;
    cout <<"Iteracyjnie: "<<czas_obl<<"s."<<endl;
    start = clock();
    rekurencyjnie(n);
    end = clock();
    czas_obl = 1.0 * (end - start) / CLK_TCK;
    cout << "Rekurencyjnie: " << czas_obl << "s." << endl;
    cout << "Wartosc: " << iteracyjnie(n);
}

 

Answer 1

Wydajność jest problemem. Trywialne dodawanie dla CPU to nic wymagającego. Przy naprawdę dużym n będzie problem.

Na marginesie, przekombinowałeś. 

long long iteracyjnie(int n) {
    long long a = 0;
    long long b = 1;
    for (int i = 0; i < n; i++){
        b += a;
        a = b - a;
    }
    return b;
}
long long rekurencyjnie(int n){
    if (n < 3) return 1;
    return rekurencyjnie(n - 2) + rekurencyjnie(n - 1);
}

 

Comments

Podkreślił bym że dodawanie to dla procka szybsza czynność, niż wywołanie funkcji (szczególnie z parametrem).

A do autora wątku - czas wykonania licz dla wielokrotnego wykonania tej samej czynności, czyli mierz czas np. tysiąckrotnego wykonania odpowiedniej funkcji.