Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

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

OrangeTree
Příspěvky: 61
Reputace:   0 
 

Složitost složených cyklů

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 :).

Offline

 

#2 06. 02. 2012 22:05

FailED
Příspěvky: 1255
Reputace:   42 
 

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

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.

Offline

 

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

Stýv
Vrchní cenzor
Příspěvky: 5711
Reputace:   215 
Web
 

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

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

Offline

 

#4 07. 02. 2012 19:32

FailED
Příspěvky: 1255
Reputace:   42 
 

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

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

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech