Matematik

A-Datastructure

03. maj 2019 af Rossa - Niveau: Universitet/Videregående

Hej derude. Jeg har en opgave, som jeg prøver at løse, men kan ikke komme til den rigtige konklusion

Opgaven lyder:
Lad T(n) betegne køretiden (runtime) for en algoritme hvor
$T(n) = \left\{\begin{matrix} 4 \ T(n/4) \ \ \ n\geq 4& \\ 1 \ \ \ \ \ \ ellers & \end{matrix}\right.$

Bevis, at T(n) ∈ O(n) (Uden tab af generalitet kan du antage, at " n is a power of 4"
Det jeg prøver er:

$T(n) = 4 \ T(n/4) = 4^2 T(n/4^2) = 4^3 T(n/4^3)=\underbrace{..}_{k-times}=4^k \ T(n/4^k)$

Nu lader
$\frac{n}{4^k} =4\\ k = log_4(n)-1$
Nu har jeg

$T(n) = 4 \ T(n/4) = 4^k \ T(n/4^k) = 4^{log_4(n)-1} \ T(n / 4^{log_4(n)-1})\\ = \frac{1}{4} \ T\left( \frac{n}{ \left( \frac{n}{4} \right )} \right ) = \frac{1}{4} \ T(4)$

det er forkert efter min forståelse

Vil nogen hjælpe med løse opgaven?
På forhånd tak

Brugbart svar (0)

Svar #1
03. maj 2019 af jnl123

Er det ikke noget med at sætte:

$n:=4^k,k\in\mathbb{N}$

Og så betragte:

$T(k)=\left\{\begin{matrix} 4T(k-1), k\geq 1\\1, ellers \end{matrix}\right.$

Brugbart svar (0)

Svar #2
03. maj 2019 af peter lind

Du skal regne den anden vej. T(4n) = 4*T(n) så T(n) = k*n

Skriv et svar til: A-Datastructure

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.