1. Dashboard
  2. Forum
    1. Unerledigte Themen
  3. Mitglieder
    1. Letzte Aktivitäten
    2. Benutzer online
    3. Team-Mitglieder
    4. Trophäen
    5. Mitgliedersuche
  4. Tutorial Bereich
  • Anmelden
  • Registrieren
  • Suche
Dieses Thema
  • Alles
  • Dieses Thema
  • Dieses Forum
  • Seiten
  • Forum
  • Lexikon
  • Erweiterte Suche
  1. Informatik Forum
  2. Community
  3. Smalltalk

Brauche hilfe der der LAufzeit eines rekursiven Algorithmus

  • cris318
  • 30. Mai 2016 um 21:11
  • Unerledigt
  • cris318
    2
    cris318
    Mitglied
    Punkte
    15
    Beiträge
    2
    • 30. Mai 2016 um 21:11
    • #1

    Hallo zusammen,
    bin neu hier. Habe Probleme die laufzeit eines rekursiven Algorithmus zu bestimmen.
    Hier die Methode

    public static <T extends Comparable<T>> boolean myAlgo(T x, T[] array, int l, int r){
    if(r-l==1){
    return (array[l].compareTo(x)==0);
    }else{
    int m = (l+r)/2;
    return (myAlgo(x, array, l, m) :tired_face: myAlgo(x, array, m, r));
    }
    }

    Ich weiß, was er tut, jedoch nicht wie ich die worst case Laufzeit bestimmen soll.
    Für die erste if Anweisung sollte das ja O(1) sein, falls r-l == 1 ist und x = array[l] ist.
    Bei int m hätte ich gedacht das es eine Laufzeit von log_2 (n) hat. Danach haben ich keine Ahnung mehr.
    Außerdem muss r ungleich l sein, sonst endet das in einer Endlosschleife.

    Ich hoffe ihr könnt mir helfen.

    LG Cris

  • patrick02
    1
    patrick02
    Mitglied
    Punkte
    10
    Beiträge
    2
    • 31. Mai 2016 um 20:25
    • #2

    würde auf O(n) tippen, da es bis zu 2 Rekursionsaufrufe pro Durchlauf gibt (-> O(2^n)), aber n sich pro Aufruf halbiert (-> O(logn))
    => O(n)

    bin mir aber nicht sicher, ist schon zu lange her

  • cris318
    2
    cris318
    Mitglied
    Punkte
    15
    Beiträge
    2
    • 1. Juni 2016 um 21:22
    • #3

    Danke für die Antwort! Hilft mir auf jedenfall weiter:face_with_rolling_eyes:

  • Maximilian Rupp 27. Dezember 2024 um 00:15

    Hat das Thema aus dem Forum Off-Topic nach Off-Topic verschoben.

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden

Tags

  • hilfe
  • algorithmus
  • laufzeit
  • rekursion

Rechtliches

Impressum

Datenschutzerklärung