---

Hej

Jeg har fået en opgave som går ud på at finde hvornår en algoritme
er bedre en anden.

Den ene algoritme har en en kørselstid?!? der svarer til 8 * n ^2
Den anden algoritme har en kørselstid der svarer til 64 * n * lg n

Spørgsmålet går ud på at finde ud hvornår den første algoritme er mere
favorable en den anden.

Jeg går ud fra at jeg skal opstille de to kørselstidspunkter som en
ulighed, og reducere den. Jeg er sidder lidt fast, så noget hjælp
kunne være tiltrængt, men her er hvad jeg er kommet frem til.

8 * n^2 <= 64 * n * lg n <=>

n^2 <= 8 * n * lg n <=>

n <= 8 lg n <=>

n/lg n <= 8

lg har basen 10 (hvis der skulle herske tvivl)

Og her sidder jeg så fast. Findes der nogen regel der kan bestemme n?

Og hvad med det omvendte? altså hvis 1/8 <= lg n / n

Jeg har brugt bruteforce metoden og kommet frem til at intervallet må
ligge imellem 2 og 6. Men det er lidt sjovere hvis jeg fremover kan
bruge en formel.

Et andet spørgsmål:

findes der en formel for at bestemme n i et fakultet. f.eks. n! = x.

På forhånd tak

aimat

---

"aimat" <meang@post.com> wrote in message
news:b74c20hui5tjm35ku3t4fr2sircbdp5seb@4ax.com...
>
> n/lg n <= 8
>

eller N = 8 * log N

> Og her sidder jeg så fast. Findes der nogen regel der kan bestemme n?

Måske en rækkeudvikling af log? Det kan jeg desværre ikke huske om
eksisterer, pinligt så meget der er glemt, når det ikke bruges.

> Jeg har brugt bruteforce metoden og kommet frem til at intervallet må
> ligge imellem 2 og 6. Men det er lidt sjovere hvis jeg fremover kan
> bruge en formel.

Prøv med:
log 4 = 0.60
8 * 0.6 = 4.8
log 4.8 = 0.68
8 * 0.68 = 5.46
...
...
...
Konvergerer mod ca. 6.507 (ikke mellem 2 og 6 !)

> findes der en formel for at bestemme n i et fakultet. f.eks. n! = x.

Der findes en approksimativ formel til at bestemme n! også for
ikke-heltallige værdier af n. Den er ikke pæn (husker jeg), og man kan nok
ikke finde den omvendte funktion.

hilsen
Uffe

---

"Uffe Kousgaard" <look_at_www.routeware.dk> writes:

> Der findes en approksimativ formel til at bestemme n! også for
> ikke-heltallige værdier af n. Den er ikke pæn (husker jeg),

Du tænker formentlig på Stirlings formel:

n! ~= sqrt(2*pi)*n^(n+1/2)^e^-n

> og man kan nok ikke finde den omvendte funktion.

Det er rigtigt, det er præcis samme problem som at løse den ligning
aimat startede med.

..Henrik

--
"Gud har skabt de hele tal, alt andet er menneskeværk" - Kronecker
"Gud har 'INTET' skabt. Alt andet er menneskeværk" - Flemming Topsøe

---

Henrik Christian Grove wrote:

> Du tænker formentlig på Stirlings formel:
>
> n! ~= sqrt(2*pi)*n^(n+1/2)^e^-n

Der findes også en lidt bedre approksimation

n! ~= sqrt((2*n+1/3)*pi)*n^n*e^(-n).

Stirling's formel kan bringes på lignende form

sqrt(2*pi)*n^(n+1/2)*e^(-n) = sqrt(2*pi*n)*n^n*e^(-n),

så man kan se, at eneste forskel er substitutionen 2*n -> 2*n+1/3.

Martin
--
http://adelic.org/

---

aimat <meang@post.com> writes:

> Hej
>
> Jeg har fået en opgave som går ud på at finde hvornår en algoritme
> er bedre en anden.
>
> Den ene algoritme har en en kørselstid?!? der svarer til 8 * n ^2
> Den anden algoritme har en kørselstid der svarer til 64 * n * lg n

Det lyder som opgave 1.2-2 i 'Introduction to algorithms' af Cormen,
Leiserson, Rivest og Stein. (opgaven var også i første udgave, men den
gider jeg ikke grave frem for at se om nummeret var det samme).

> lg har basen 10 (hvis der skulle herske tvivl)

Hvorfor tror du det? Alle steder jeg har set lg brugt, har det været som
betegnelse for logaritmen med grundtal 2.

> Og her sidder jeg så fast. Findes der nogen regel der kan bestemme n?

Nej, ligningen kan ikke løses analytisk.

..Henrik

--
Jacob: Because the theoreticians told me.
Prof. Vassilicos: Why do you believe theoreticians?

---

Henrik Christian Grove <grove@sslug.dk> writes:

> Hvorfor tror du det? Alle steder jeg har set lg brugt, har det været som
> betegnelse for logaritmen med grundtal 2.

Og hvis jeg har ret i at det er grundlag 2 der tænkes på i opgaven, kan
det betale sig at bruge samme gættestrategi som Stefan Holm anvendte da
han skulle finde det mindste n for hvilket n! ender på præcis 10
nuller i den første DatA-time han havde (med mig som
instruktor).

..Henrik

XFut: dk.snak.off-topic

--
Jacob: Because the theoreticians told me.
Prof. Vassilicos: Why do you believe theoreticians?

---

On 08 Feb 2004 15:06:33 +0100, Henrik Christian Grove <grove@sslug.dk>
wrote:

>aimat <meang@post.com> writes:
>
>> Hej
>>
>> Jeg har fået en opgave som går ud på at finde hvornår en algoritme
>> er bedre en anden.
>>
>> Den ene algoritme har en en kørselstid?!? der svarer til 8 * n ^2
>> Den anden algoritme har en kørselstid der svarer til 64 * n * lg n
>

>Det lyder som opgave 1.2-2 i 'Introduction to algorithms' af Cormen,
>Leiserson, Rivest og Stein. (opgaven var også i første udgave, men den
>gider jeg ikke grave frem for at se om nummeret var det samme).
>

hehe det er fra CLRS, som du har bemærket...

>> lg har basen 10 (hvis der skulle herske tvivl)
>
>Hvorfor tror du det? Alle steder jeg har set lg brugt, har det været som
>betegnelse for logaritmen med grundtal 2.

Ja ved nærmere granskning så er det faktisk log med base 2

>
>> Og her sidder jeg så fast. Findes der nogen regel der kan bestemme n?
>
>Nej, ligningen kan ikke løses analytisk.


Hmmmm... vil det så sige at det skal løses via brute force... altså at
man prøver at approximere eller prøver samtlige kombinationer

>
>.Henrik

---

aimat <meang@post.com> writes:

> Hmmmm... vil det så sige at det skal løses via brute force... altså at
> man prøver at approximere eller prøver samtlige kombinationer

Som Henning siger er svaret et heltal (det giver ikke mening at sortere
67,4 tal), og du ved også at der kun er et (interessant) skæringspunkt,
så tager det ikke så lang tid at finde løsningen ved at udregne 8*n^2 og
64*n*lg n for nogle n og se at hvis 8*n^2 er størst var din n værdi over
skæringspunktet ellers var den under.

(Og jeg synes det er en elendig opgave, folk kommer let til at bruge alt
for meget tid på at prøve at løse ligningen)

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

aimat <meang@post.com> writes:

> Jeg går ud fra at jeg skal opstille de to kørselstidspunkter som en
> ulighed, og reducere den. Jeg er sidder lidt fast, så noget hjælp
> kunne være tiltrængt, men her er hvad jeg er kommet frem til.
>
> 8 * n^2 <= 64 * n * lg n <=>
>
> n^2 <= 8 * n * lg n <=>
>
> n <= 8 lg n <=>
>
> n/lg n <= 8
>
> lg har basen 10 (hvis der skulle herske tvivl)
>
> Og her sidder jeg så fast. Findes der nogen regel der kan bestemme n?

Hvis n er reelt, så kan du sikkert bruge Newtons metode. Der er vist
også en iterationsformel der virker.

Hvis du er helt vild med at få et resultat der ser analytisk ud, kan
du prøve at udtrykke din løning ved hjælp af Lamberts W-funktion
W(x). Den er løsning til ligningen:

x = W(x) * exp(W(x))

Hvis du har adgang til Maple eller Mathematica, så tror jeg at den
løser det for dig uden at brokke sig.

http://mathworld.wolfram.com/LambertW-Function.html

--
Niels L Ellegaard http://dirac.ruc.dk/~gnalle/

---

Scripsit aimat <meang@post.com>

> n/lg n <= 8

> Og her sidder jeg så fast. Findes der nogen regel der kan bestemme n?

Blot for nu at skære de andre svar ud i pap: Dit n er et heltal. Vi
ved at grænsen er under 8. 7 forskellige muligheder kan du nok prøve
dig frem med i håden uden at slide din lommeregner helt op.

--
Henning Makholm "... popping pussies into pies
Wouldn't do in my shop
just the thought of it's enough to make you sick
and I'm telling you them pussy cats is quick ..."