Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Laufzeit bestimmen?

Laufzeit bestimmen?

Universität / Fachhochschule

Tags: Algorithmus, Laufzeitkomplexität, Lauzeit

heeey aktiv_icon

14:30 Uhr, 27.05.2018

Hallo,

ich habe ein paar kleinen Algorithmen und will ihre Laufzeiten bestimmen. Ich habe schon vieles dazu gelesen und auch vertanden, brauche nur eure Hilfe.
Sagen wir, wir haben folgendes:

function(n)

{

(n < 1) O (1)

return

1; O (1)

return function(n/4)

+

function(n/4);

};

Also mich interessiert jetzt, wie oft sich selbst die Fuktion aufruft.
Ich weiß, man kann die Laufzeit mit Hilfe der Master Theorem bestimmen.
Ist es korrekt, wenn ich sage, dass

T (n) = a,

(oder

1),

für

n < 1

T (n) = b + T (\frac{n}{4}) + T (\frac{n}{4}), b

ist eine konstante

und wenn es stimmt, soll ich dann eine geschlossene Form finden? Wie geht es?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."