Matematické Fórum

OrangeTree

Ahoj :).

Nedokáži určit složitost těchto cyklů...

for(i=2; i<=n; i*=i)
for(j=0; j<n; j++)
sum++;

Vnitřní cyklus se provede n-krát, ale nevím si rady s tím vnějším. Kdyby to šlo popsat nějak podrobněji...

Díky :).

FailED · 06. 02. 2012 22:05

Při prvním průchodu bude i 2, při druhém 4, ... při m-tém 2^m, zastaví se, když 2^m>n teda m>logn.

Stýv · 07. 02. 2012 10:03 — Editoval Stýv (07. 02. 2012 10:05)

nebude to při m-tém průchodu spíš $\underbrace{((((2^2)^.)^.)^.)^2}_{m-\text{krát}}$ ?

FailED · 07. 02. 2012 19:32

Ajo, omlouvám se. Tedy $2^{2^m}$

Matematické Fórum

#1 06. 02. 2012 22:01 — Editoval OrangeTree (06. 02. 2012 22:01)

Složitost složených cyklů

#2 06. 02. 2012 22:05

Re: Složitost složených cyklů

#3 07. 02. 2012 10:03 — Editoval Stýv (07. 02. 2012 10:05)

Re: Složitost složených cyklů

#4 07. 02. 2012 19:32

Re: Složitost složených cyklů

Zápatí