Rekursive Fibonacci Zahlen in CPP Laufzeit bestimmen oder berechnen?

wob

@Saya sagte in Rekursive Fibonacci Zahlen in CPP Laufzeit bestimmen oder berechnen?:

Wie bestimme ich mit einer rekursive fibonacci Code in cpp die Laufzeit?

Am besten gar nicht.

Wie man fibonacci richtig macht, siehe Video von Sean Parent: https://www.youtube.com/watch?v=QIHy8pXbneI&t=2107s

Bzw. wenn du alle Werte nacheinander ausgeben willst, dann natürlich einfach 2 Variablen und ne loop.

omggg

Pardon, besser so:

unsigned long long fib_recursive(int n) {
  if (n <= 2) {
    return 1;
  }
  return fib_recursive(n - 1) + fib_recursive(n - 2);
}

static void fib25(benchmark::State& state) {
  int n = 25;
  for (auto _ : state) {
    unsigned long long f = fib_recursive(n);
    benchmark::DoNotOptimize(f);
  }
}
BENCHMARK(fib25);

static void fib50(benchmark::State& state) {
  int n = 50;
  for (auto _ : state) {
    unsigned long long f = fib_recursive(n);
    benchmark::DoNotOptimize(f);
  }
}
BENCHMARK(fib50);

static void fib100(benchmark::State& state) {
  int n = 100;
  for (auto _ : state) {
    unsigned long long f = fib_recursive(n);
    benchmark::DoNotOptimize(f);
  }
}
BENCHMARK(fib100);

omggg

@wob sagte in Rekursive Fibonacci Zahlen in CPP Laufzeit bestimmen oder berechnen?:

Wie man fibonacci richtig macht, siehe Video von Sean Parent:

@wob Ich glaube, die Funktion von @Saya hat i-wie eine Macke.

omggg

Ach sorry ich bin einfach zu doof:

https://oeis.org/A000045

Die Folge wächst einfach zu schnell! fib100 ist Quatsch.

omggg

So, nun noch einmal richtig:

unsigned long long fib_recursive(unsigned long long n) {
  if (n <= 2) {
    return 1;
  }
  return fib_recursive(n - 1) + fib_recursive(n - 2);
}

static void fib1(benchmark::State& state) {
  int n = 15;
  for (auto _ : state) {
    auto f = fib_recursive(n);
    benchmark::DoNotOptimize(f);
  }
}
BENCHMARK(fib1);

static void fib2(benchmark::State& state) {
  int n = 16;
  for (auto _ : state) {
    auto f = fib_recursive(n);
    benchmark::DoNotOptimize(f);
  }
}
BENCHMARK(fib2);

static void fib3(benchmark::State& state) {
  int n = 17;
  for (auto _ : state) {
    auto f = fib_recursive(n);
    benchmark::DoNotOptimize(f);
  }
}
BENCHMARK(fib3);

Optimierungen: None

https://quick-bench.com/q/CcwcZ5cIFsUDfzE2IcjG7qooSSk

Ergebnis: Wenn sich n um 1 erhöht, braucht die cpu fast doppelt so lange.

Th69

Dass die Laufzeit exponentiell ist ( $O(2^n)$ ), liegt an der doppelten Berechnung von fib(n-2) je Iteration (fib(n-1)ruft ja wiederum fib(n-2) auf).
Schneller geht dies mit der Speicherung der berechneten Werten: Recursive Fibonacci in c++ using std::map.

Schlangenmensch

@omggg Wenn du schon so weit ist, könntest du die Laufzeit der rekursiven Version mal mit einer Iterativen Lösung und mit der Version aus dem Video vergleichen.

@Saya Zeitmessungen kann man mit std::chrono erledigen:

  auto t1 = std::chrono::high_resolution_clock::now();
  /*
  * The code to measure
  */
  auto t2 = std::chrono::high_resolution_clock::now();
    /* Getting number of milliseconds as an integer. */
  auto ms_int = duration_cast<std::chrono::milliseconds>(t2 - t1);
  std::cout << ms_int;

wob

@omggg sagte in Rekursive Fibonacci Zahlen in CPP Laufzeit bestimmen oder berechnen?:

Optimierungen: None

Klingt sehr sinnvoll für eine Zeitmessung.
Nicht!

omggg

@wob sagte in Rekursive Fibonacci Zahlen in CPP Laufzeit bestimmen oder berechnen?:

@omggg sagte in Rekursive Fibonacci Zahlen in CPP Laufzeit bestimmen oder berechnen?:

Optimierungen: None

Klingt sehr sinnvoll für eine Zeitmessung.
Nicht!

Der Compiler kann da schon stark optimieren bei O3 ....

Für mich ist unklar, was hier wie gemessen und/oder verglichen werden soll! Mit Optimierungen: None spiegelt die Laufzeit des Codes die Algorithmenlaufzeit (fast 1:1) wider.

Quiche Lorraine

@Saya
Laufzeit hängt stark von der Komplität ab. Bei der Laufzeit fragt man sich wieviel Zeit eine Funktion benötigt, während man bei der Komplexität sich fragt, wieviele Schritte eine Funktion benötigt.

Wenn du das folgende Test-Programm mal laufen lässt, so wirst du sehen dass die Anzahl der Schritte pro Stufe (um 1 erhöhtes n) grob um den Faktor 1.61 erhöhen.

#include <cstdio>
#include <string>
#include <iostream>

#include <iostream>
#include <chrono>

unsigned long long fib_recursive_test(unsigned long long n, unsigned long long& Steps) {
	Steps++;
	if (n <= 2) {
		return 1;
	}
	return fib_recursive_test(n - 1, Steps) + fib_recursive_test(n - 2, Steps);
}

// Spielprojekt damit wir ein Gefühl für Funktionen mit exponentieller Komplexität bekommen

int main() {
	unsigned long long Value;
	unsigned long long Steps;
	unsigned long long LastSteps = 0;
	
	for (unsigned long long n = 0; n < 75; n++)
	{
		Steps = 0;
		Value = fib_recursive_test(n, Steps);
		std::cout << "Fibonacci-Zahl von " << n << " ist " << Value << " Anzahl Schritte: " << Steps;
		if (LastSteps != 0)
			std::cout << " Zunahme Faktor = " << static_cast<double>(Steps) / LastSteps;
		std::cout << std::endl;
		LastSteps = Steps;
	}
	return 0;
}

omggg

Als Erstes sollten wir mal die Begriffe (theoretische/tatsächliche ) Laufzeit, Komplexität, Rechenzeit und Kosten im Rahmen dieses Threads definieren! Weiterhin macht es keinen Sinn, die rekursive mit der iterativen Variante zu vergleichen.