0 Daumen
136 Aufrufe

Ich wollte fragen, ob meine Vermutung zur Laufzeit passen.

function A1(n):
if n ≤1 then return 1
fi
x := A1(⌊n/2⌋)+A1(⌈n/2⌉)
y :=0
for i =1 to x do
  y := y +1
od
return y

Da x = n ist (wegen ⌊n/2⌋+⌈n/2⌉ = n), hat die for Schleife eine Laufzeit von Theta(n).

function A2(n):
if n ≤1 then return n
 fi
 x := A2(n−1)
y :=1
for i =1 to ⌊√n⌋ do
y := y +1
od
return x+y

Das heißt x wird n Mal aufgerufen und die for Schleife ist in O(n), deshalb sage ich hier auch Theta(n).

function A3(n):
x :=0;
for i =1 to n do
 for k = i−3 to 2i do
for l= k to max{i,k +3} do
x := x+1
od
od
od
return x+A3(⌊n/2⌋)

Die drei Vorschleifen habe eine Laufzeit von O(n^3) und da n immer halbiert wird mit jedem Aufruf, sage ich Theta(n^3 log n).

Hoffe es passt so:) Danke im Voraus:D

von

1 Antwort

0 Daumen

Ich denke man kann das durchaus so machen, wie du das aufgeschrieben hast.

PS: Das sind ein paar nette Beispiele!

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community