• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z odmierzaniem czasu

Object Storage Arubacloud
0 głosów
335 wizyt
pytanie zadane 10 października 2021 w C i C++ przez yato_ Początkujący (350 p.)

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);
}

 

1 odpowiedź

+1 głos
odpowiedź 10 października 2021 przez tkz Nałogowiec (42,000 p.)
wybrane 10 października 2021 przez yato_
 
Najlepsza

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);
}

 

komentarz 11 października 2021 przez Oscar Nałogowiec (29,320 p.)
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.

Podobne pytania

0 głosów
1 odpowiedź 467 wizyt
pytanie zadane 28 grudnia 2016 w C i C++ przez vega Użytkownik (510 p.)
0 głosów
3 odpowiedzi 475 wizyt
pytanie zadane 1 lipca 2016 w C i C++ przez niezalogowany
0 głosów
1 odpowiedź 495 wizyt
pytanie zadane 28 września 2016 w C i C++ przez Arkadiusz Sieczak Początkujący (400 p.)

92,690 zapytań

141,603 odpowiedzi

320,098 komentarzy

62,050 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...