---

Hej

Jeg har fået taget mig et rigtig hyggekursus i algoritmik og
datastructurer... indtil der gik asymptote i den.

Jeg synes jeg mangler forståelsen for helt præcist hvordan man kan
ræsonere frem til en asymtptoisk tæt grænse (er det ikke det det
hedder på dansk asymptotic tight bound (theta notationen))

Spørgsmål 1: Vil der altid være en asymptotisk tæt grænse til enhver
funktion?

Spørgsmål 2: Hvis ja. hvis man har en nedre grænse som er logaritmisk
d.v.s. omega(lg n) og O(2^n) og en øvre grænse som en eksponential.
Hvad er den theta i den sammenhæng, og hvordan finder man frem til
den?

Spørgsmål 3: Anvendes der normale regne regler når man adderer,
subtrahere, divederer og multiplicerer store O og theta og omega

f.eks:

O(1) + O(1) = O(2) = O(1)
O(n) * O(lg n) = O(n lg n) = O(1)

og hvad med

O(1) + theta(1) = ?

Spørgsmål 4:

Hvis de normale regne regler gælder:

Er der så nogen forskel mellem O(1 + 1) og O(1) + O(1) ?

Sprøgsmål 5: En af de gamle hjemmeopgave hed:

let f(n) og g(n) be asymptotical nonnegaative functions. Using the
basic definition of theta-notation, prove that max(f(n), g(n)) =
theta(f(n) + g(n)).

Jeg har ingen ide om hvor jeg skal starte er der nogen, som kan give
mig et hint

mvh

Meang

---

aimat <meang@post.com> writes:

> ræsonere frem til en asymtptoisk tæt grænse (er det ikke det det
> hedder på dansk asymptotic tight bound (theta notationen))

Bortset fra at det staves asymptotisk.

> Spørgsmål 1: Vil der altid være en asymptotisk tæt grænse til enhver
> funktion?

Ja, en funktion vil altid være en symptotisk tæt grænse for sig selv,
men det er ret uinteressant.

Derimod vil en funktion som x^2+x+x^2*sin(x) ikke have nogen interessant
asymptotisk tæt grænse (den er omega(n) og o(n^2)).

> Spørgsmål 2: Hvis ja. hvis man har en nedre grænse som er logaritmisk
> d.v.s. omega(lg n) og O(2^n) og en øvre grænse som en eksponential.
> Hvad er den theta i den sammenhæng, og hvordan finder man frem til
> den?

Det kan man ikke generelt.

> Spørgsmål 3: Anvendes der normale regne regler når man adderer,
> subtrahere, divederer og multiplicerer store O og theta og omega

Nej.

> O(1) + O(1) = O(2) = O(1)

Der er ikke noget decideret forkert i det, men det er forkert at tro at
de to et-taller kan lægges sammen.

> O(n) * O(lg n) = O(n lg n) = O(1)

O(n lg n) != O(1).

> O(1) + theta(1) = ?

O(1)

> let f(n) og g(n) be asymptotical nonnegaative functions. Using the
> basic definition of theta-notation, prove that max(f(n), g(n)) =
> theta(f(n) + g(n)).
>
> Jeg har ingen ide om hvor jeg skal starte er der nogen, som kan give
> mig et hint

Definitionen af Theta siger at der skal være en nedre og en øvre grænse,
find dem en ad gangen.

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

---

On 05 Apr 2004 14:30:07 +0200, Henrik Christian Grove <grove@sslug.dk>
wrote:

>aimat <meang@post.com> writes:
>
>> Spørgsmål 2: Hvis ja. hvis man har en nedre grænse som er logaritmisk
>> d.v.s. omega(lg n) og O(2^n) og en øvre grænse som en eksponential.
>> Hvad er den theta i den sammenhæng, og hvordan finder man frem til
>> den?
>
>Det kan man ikke generelt.

Når du sigere at det kan man ikke generelt betyder det at der er ikke
findes nogen generel måde at finde frem til theta på?
eller at der ikke findes en theta til omega(lg n) og O(2^n)?

Og hvis der ikke findes en generel måde at finde theta på. Hvordan
ræsonerer folk sig frem til theta?

>
>> Spørgsmål 3: Anvendes der normale regne regler når man adderer,
>> subtrahere, divederer og multiplicerer store O og theta og omega
>
>Nej.

Findes der overhovedet nogle regler om at addere O, theta og Omega?

>
>> O(1) + O(1) = O(2) = O(1)
>
>Der er ikke noget decideret forkert i det, men det er forkert at tro at
>de to et-taller kan lægges sammen.

Hvad ville man så skrive? O(1) + O(1) = O(1) ?

>
>> O(n) * O(lg n) = O(n lg n) = O(1)
>
>O(n lg n) != O(1).
>
>> O(1) + theta(1) = ?
>
>O(1)


mvh

Meang

---

aimat <meang@post.com> writes:

> On 05 Apr 2004 14:30:07 +0200, Henrik Christian Grove <grove@sslug.dk>
> wrote:
>
> >aimat <meang@post.com> writes:
> >
> >> Spørgsmål 2: Hvis ja. hvis man har en nedre grænse som er logaritmisk
> >> d.v.s. omega(lg n) og O(2^n) og en øvre grænse som en eksponential.
> >> Hvad er den theta i den sammenhæng, og hvordan finder man frem til
> >> den?
> >
> >Det kan man ikke generelt.
>
> Når du sigere at det kan man ikke generelt betyder det at der er ikke
> findes nogen generel måde at finde frem til theta på?

Ja.

> eller at der ikke findes en theta til omega(lg n) og O(2^n)?

Ingen entydig. Alle funktioner der er Theta(n^k) (for ethvert k) er
omega(lg n) og O(2^n).

> Og hvis der ikke findes en generel måde at finde theta på. Hvordan
> ræsonerer folk sig frem til theta?

Udfra viden om det hvis asymptotiske udvikling behandles.

> >> Spørgsmål 3: Anvendes der normale regne regler når man adderer,
> >> subtrahere, divederer og multiplicerer store O og theta og omega
> >
> >Nej.
>
> Findes der overhovedet nogle regler om at addere O, theta og Omega?

Addition er forholdsvis overkommeligt, det er bare at lægge funktionerne
sammen.

> >> O(1) + O(1) = O(2) = O(1)
> >
> >Der er ikke noget decideret forkert i det, men det er forkert at tro at
> >de to et-taller kan lægges sammen.
>
> Hvad ville man så skrive? O(1) + O(1) = O(1) ?

Ja.

..Henrik

--
"The ultimate goal of mathematics is to eliminate all need for
intelligent though" - Graffiti af ukendt i 'Concrete Mathematics'

---

On 05 Apr 2004 17:46:27 +0200, Henrik Christian Grove <grove@sslug.dk>
wrote:

>aimat <meang@post.com> writes:
>
>> On 05 Apr 2004 14:30:07 +0200, Henrik Christian Grove <grove@sslug.dk>
>> wrote:
>>
>> >aimat <meang@post.com> writes:
>> >
>> >> Spørgsmål 2: Hvis ja. hvis man har en nedre grænse som er logaritmisk
>> >> d.v.s. omega(lg n) og O(2^n) og en øvre grænse som en eksponential.
>> >> Hvad er den theta i den sammenhæng, og hvordan finder man frem til
>> >> den?
>> >
>> >Det kan man ikke generelt.
>>
>> Når du sigere at det kan man ikke generelt betyder det at der er ikke
>> findes nogen generel måde at finde frem til theta på?
>
>Ja.
>
>> eller at der ikke findes en theta til omega(lg n) og O(2^n)?
>
>Ingen entydig. Alle funktioner der er Theta(n^k) (for ethvert k) er
>omega(lg n) og O(2^n).


Vil det så sige at hvis man får stillet en opgave. f.eks. find den
asymptotic tight bound, så mener man nødvengivis ikke en theta
funktion (kalder man det det?),

man kan også specificere denne tætte grænse i henholdsvis en
omega(f(n)) og O(g(n)) funktion, hvor f(n) ikke nødvendigvis behøver
at være lig med g(n).

Det jeg nok prøver at sige er:

at en asymptotic tight bound ikke nødvendigvis behøver at være en
grænse hvor funktionen er ens både i den øvre og nedre grænse.

og findes der nogle "læsevenlig bog" om asymptotic analyse specielt om
theta

og en milliong gange tak for svarene

meang

---

aimat <meang@post.com> writes:

> On 05 Apr 2004 17:46:27 +0200, Henrik Christian Grove <grove@sslug.dk>
> wrote:
>
> >aimat <meang@post.com> writes:

> >> eller at der ikke findes en theta til omega(lg n) og O(2^n)?
> >
> >Ingen entydig. Alle funktioner der er Theta(n^k) (for ethvert k) er
> >omega(lg n) og O(2^n).
>
>
> Vil det så sige at hvis man får stillet en opgave. f.eks. find den
> asymptotic tight bound, så mener man nødvengivis ikke en theta
> funktion (kalder man det det?),

Nej. En asymptotisk tæt grænse kan per definition udtrykkes som
Theta(<noget>), men hvis du bliver bedt om at finde en asymptotisk tæt
grænse vil du også få flere oplysninger end blot et Omega og et O.

> man kan også specificere denne tætte grænse i henholdsvis en
> omega(f(n)) og O(g(n)) funktion, hvor f(n) ikke nødvendigvis behøver
> at være lig med g(n).

Nej, det er ikke tæt.

> Det jeg nok prøver at sige er:
>
> at en asymptotic tight bound ikke nødvendigvis behøver at være en
> grænse hvor funktionen er ens både i den øvre og nedre grænse.

Det er forkert.

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