Site icon blog.tomhanoldt.info

Fibonacci

Entstanden im Algorithmenkurs github

Ziel: Laufzeitvergleich(O-Notation) verschiedener Algorithmen zur Bestimmung von Fibonaccifolgen.
Testbedingungen: Es wird einmal der Fall einer Einzelberechnung betrachtet, und vor allem für die um Cashing erweiterten Algorithmen mehrfache Berechnung.
Algorithmen: FibonacciFormel f(n)=O(1)

FibonacciIterativ f(n)=O(n)

FibonacciIterativCashed f(n)=O(n)     *für eine Berechnung

FibonacciRekursiv f(n)=O(1.62^n)

FibonacciRekursivCashed f(n)=O(n)     *für eine Berechnung

#TODO FibonacciMatrix

Ergebnis: Was man erwartet, zu bemerken ist, dass der FibonacciRekursivCashed-Algorithmus mit n wächst und im Fall von der Berechnung einer Folge von Fibonacci-Zahlen sogar erheblich Aufwand spart. Der FibonacciIterativCashed-Algorithmus hingegen, kann nur Vorteile vom Cashing nutzen, wenn die gleiche Zahl berechnet wird.

*wer die Tests nachvollziehen will, kann das fib Paket runterladen(github) und die Gui.java “starten”

fib.FibonacciRecursiveCashed.java

public class FibonacciRecursiveCashed
{
	private static HashMap<Integer,Long> operationCash = new HashMap<Integer,Long> (100);

	public static long getFibFromPosition(int position)
	{
		Helper.addCallInformation("FibonacciRecursiveCashed init");

		if(position == 0)
		{
			return 0;
		}

		return _getFibFromPosition(
					Math.abs(position));
	}

	protected static long _getFibFromPosition(int position)
	{
		if(position < 2)
		{
			Helper.addCallInformation("FibonacciRecursiveCashed : return 1");

			return 1;
		}

		if(operationCash.containsKey(position))
		{
			return operationCash.get(position);
		}

		Helper.addCallInformation("FibonacciRecursiveCashed : not cashed for "+position);

		long result = _getFibFromPosition(position - 1) + _getFibFromPosition(position - 2);

		operationCash.put(position,result);

		return result;
	}

	public static void clearCash()
	{
		operationCash.clear();
	}
}
Exit mobile version