Algoritmi - časovna zahtevnost

Klik

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.

Od kod dobimo tole:
a^4n^4 = a^4 T

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.

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 ;)

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.