Forum » Šola » Algoritmi - časovna zahtevnost
Algoritmi - časovna zahtevnost
rudi83 ::
Nek problem ima časovno zahtevnost reda n^4. V nekem času T lahko rešimo problem velikosti n1. Za koliko večji problem lahko rešimo v taistem času T, če se čas trajanja ene operacije zmanjša za 100-krat.
Za odgovor se v naprej lepo zahvaljujem
LP
rudi
Za odgovor se v naprej lepo zahvaljujem
LP
rudi
- premaknil iz Pomoč in nasveti: gkovac ()
joze67 ::
Enakovredno vprašanje: koliko večji problem lahko rešim v 100T časa. In ker je algoritem n^4, lahko rešim v 100T časa (an) velik problem. Torej je 100T = (an)^4 = a^4n^4 = a^4 T => a^4 = 100 => a=sqrt(10).
Torej lahko s 100x hitrejšim reševanjem rešiš 3,16x večji problem.
Torej lahko s 100x hitrejšim reševanjem rešiš 3,16x večji problem.
FireSnake ::
Kaj pa kaj takega:
casovna zahtevnost je 2^n; probelm n1 lahko resis v casu T. V koliksnem casu lahko resis isti problem z 100-krat hitrejsim racunalnikom?
Neka podobna viza bo, a kdo ve?
Edit: je tole prava resitev?
Rešitev: n2 = n1 + 6,64 pac po kodi 2^n2=100×2^n1 ... ve kdo postopek?
casovna zahtevnost je 2^n; probelm n1 lahko resis v casu T. V koliksnem casu lahko resis isti problem z 100-krat hitrejsim racunalnikom?
Neka podobna viza bo, a kdo ve?
Edit: je tole prava resitev?
Rešitev: n2 = n1 + 6,64 pac po kodi 2^n2=100×2^n1 ... ve kdo postopek?
Poglej in se nasmej: vicmaher.si
Zgodovina sprememb…
- spremenilo: FireSnake ()
Senitel ::
Povezava med n in T je: n^4=T
Zanima te: (an)^4=100T
Torej:
(an)^4=100T
a^4n^4=100T
a^4T=100T (ker T=n^4)
a^4=100
a=sqrt(10)
Za tvoj primer: 2^n=T
Zanima te: 2^(an)=100T
Torej:
2^(an)=100T
2^(an)=100*2^n
an*ln(2)=n*ln(200)
a=ln(200)/ln(2)=7,64...
Torej 7,64* vecji problem ali pa isti problem v 1/7,64 casa.
Zanima te: (an)^4=100T
Torej:
(an)^4=100T
a^4n^4=100T
a^4T=100T (ker T=n^4)
a^4=100
a=sqrt(10)
Za tvoj primer: 2^n=T
Zanima te: 2^(an)=100T
Torej:
2^(an)=100T
2^(an)=100*2^n
an*ln(2)=n*ln(200)
a=ln(200)/ln(2)=7,64...
Torej 7,64* vecji problem ali pa isti problem v 1/7,64 casa.
FireSnake ::
Pa ti si zakon! 
(zdaj zgleda pa preprosto)
HVALA!
(zdaj zgleda pa preprosto)HVALA!
Poglej in se nasmej: vicmaher.si
Zgodovina sprememb…
- spremenilo: FireSnake ()
FireSnake ::
Z eno malo napakico:
2^(an)=100*2^n
ni
an*ln(2)=n*ln(200)
ampak je
an*ln(2)=n*ln(2)*ln100
Ampak, nic ne de .... si me spravil na pravo pot in je zdaj stvar popolnoma jasna ;)
2^(an)=100*2^n
ni
an*ln(2)=n*ln(200)
ampak je
an*ln(2)=n*ln(2)*ln100
Ampak, nic ne de .... si me spravil na pravo pot in je zdaj stvar popolnoma jasna ;)
Poglej in se nasmej: vicmaher.si
Zgodovina sprememb…
- spremenilo: FireSnake ()
Senitel ::
True, ampak n*ln(2)*ln(100) tudi ni prav. Logaritmirat moras celo desno stran torej: ln(100*2^n)=ln(100)+ln(2^n)=ln(100)+n*ln(2)
Kar rahlo zakomplicira vse skup
Kar rahlo zakomplicira vse skup
FireSnake ::
Res je
Pa se eno napakico sem odkril: a^m*a^+n = a^(m+n)
Torej (an)^4 != a^4n^4.
Ampak, kot ze receno, ni problema, ker so me primeri spravili na pravo pot.
Pa se eno napakico sem odkril: a^m*a^+n = a^(m+n)
Torej (an)^4 != a^4n^4.
Ampak, kot ze receno, ni problema, ker so me primeri spravili na pravo pot.
Poglej in se nasmej: vicmaher.si
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | matematika-zaporedja (strani: 1 2 )Oddelek: Šola | 6391 (5227) | lebdim |
| » | Matematika: Deljivost naravnih in celih števil.Oddelek: Šola | 3231 (3033) | lebdim |
| » | [Naloga] - Algoritmi, časovna kompleksnostOddelek: Programiranje | 6982 (3168) | WarpedGone |
| » | Matematika spl. matura 2011 (strani: 1 2 )Oddelek: Šola | 9452 (8074) | hexor |
| » | Problem pri matematikiOddelek: Šola | 2927 (2151) | SaXsIm |