Schlagwort-Archive: Fakultät

Algorithmen und Datenstrukturen: O-Notation / Komplexität der rekursiven Fakultät

Der Algorithmus

Bei der rekursiven Fakultät handelt es sich um einen rekursiven Funktionsaufruf:

package AlgoDat;
 
public class RekursiveFakultaet {
    // Zu sortierendes Array
     
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static RekursiveFakultaet program;
 
    public long berechneFakultaet(int teilFakultaet)
    {
        // Abbruchbedingung der Rekursion wenn 1 erreicht ist
        if (teilFakultaet == 1) return 1;
 
        // Multipliziere rekursiv f(n) = n * f(n - 1) bis 1
        return teilFakultaet * berechneFakultaet(teilFakultaet - 1);
    }
 
    // Konstruktor
    public RekursiveFakultaet()
    {
        System.out.println(this.berechneFakultaet(25) + "");        
    }
 
    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new RekursiveFakultaet();
    }
}

Ausgabe

7034535277573963776

Komplexität: O-Notation (Ordnung)

Der rekursive Aufruf dieser Art kann als primitiv rekursiven Klasse gezählt werden und besitzt die lineare Komplexität / O-Notation: