---

Hej NG

hvorfor kan man ikke tage log på 0 eller negative værdier ?

hvorfor har er binær søgning (i fx et sorteret array af størrelse n) har
tidskompleksitet log(n) ?

Jeg spør' bare
--
Mvh. Anders Jacobsen
www.ichtys.dk

---

Det var jo bare super, og fyldt med stave-dummerter!
Prøver lige igen...

Hvorfor kan man ikke tage Log på 0 eller negative værdier ?

hvorfor har en binær søgning (i fx et sorteret array af størrelse n)
tidskompleksitet log(n) ?

Mvh. Anders Jacobsen

---

Anders Jacobsen skrev:

>hvorfor kan man ikke tage log på 0 eller negative værdier ?

Fordi ligegyldigt hvilken potens man opløfter f.eks. 10 i, så
bliver resultatet aldrig 0 eller negativt. Og titalslogaritmen
angiver netop den potens som 10 skal opløftes i for at give
tallet. Eksempel:

   log10(1000) = 3
fordi   10^3 = 1000

   log10(2) = 0,30103
fordi   1^0^,30103 =~ 2

>hvorfor har er binær søgning (i fx et sorteret array af størrelse n) har
>tidskompleksitet log(n) ?

At søge 1024 elementer igennem sekventielt kræver i værste fald
1024 søgninger og i snit 512.

Når man søger binært, halverer man mængden hver gang. Det vil
altså i værste fald tage 10 søgninger at undersøge 1024 elementer
fordi 2^10 = 1024.

Jamen hov! Det minder jo om det med logaritmerne fra før ...

   log2(1024) = 10
fordi   2^10 = 1024

Når man snakker tidskompleksitet, er man ligeglad med konstanter,
så om man beregner log(1024) eller log2(1024) er ligemeget.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>
> >hvorfor kan man ikke tage log på 0 eller negative værdier ?
>
> Fordi ligegyldigt hvilken potens man opløfter f.eks. 10 i, så
> bliver resultatet aldrig 0 eller negativt. Og titalslogaritmen
> angiver netop den potens som 10 skal opløftes i for at give
> tallet.

Netop.

Det skal dog siges at hvis man arbejder med *komplekse* tal, så har
ligningen

10^z = k

altid uendeligt mange komplekse tal z som løsninger når bare k ikke er
nul. Dvs. at log10(k) giver en vis mening når blot k ikke er nul. Man
skal bare vælge sig et område som man foretrækker z inden for, nemlig
et passende vandret bånd i den komplekse plan.

Eksempel: log10(-1000) = 3 + i·pi·log10(e)
(eller generelt log10(-1000) = 3 + i·(2n-1)·pi·log10(e) hvor n er hel).

Det svarer lidt til at man skal vælge en hovedværdi når man i det
reelle tilfælde vil have invers sinus af et tal til kun at svare til
én vinkel.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)