Laufzeitproblem



  • Hab ein Problem bei der Laufzeitkomplexität von einem Algorithmus. Dabei handelt es sich um eine nichtlineare Rekursion.
    Die rekursive Definition lautet wie folgt:

    f(n)={2, für n<3 | 2*f(n-1)-f(n-2)+f(n-3) mit n € |N

    Den Rekursionsbaum habe ich soweit mit allem was dazugehört schon gemacht. Mit dem Speicher hab ich auch schon alles abgearbeitet.
    Aber irgendwie komme ich bei der Laufzeit nicht weiter. Hab nichtmal einen Ansatz dafür. Ich vermute ja 'ne Laufzeit zwischen polynomialer Laufzeit und exponentieller Laufzeit. Finde aber keinen Ansatz das zu beweisen 😞

    Schon einmal danke für eure Bemühungen 🙂



  • Mit einem ganz naiven rekursiven Ansatz sieht das sehr nach einer exponentiellen Laufzeit ab. (O(3^n))

    Du kannst das ganze aber mit einem iterativen Ansatz auf lineare Laufzeit bringen (O(n))


Log in to reply