1.4

[Lillipip]

Ich diskutiere gerade mit einem Freund und wir sind uns nicht einig, was da raus kommt... Stimmt das?

theta (n!) < theta (n^n)
theta (log3 (n)) > theta (log4(n))
theta (dritte wurzel aus n) < theta (vierte wurzel aus n)
theta (3^n) > theta (n^3)

[spjoe]

die dritte wurzel von n ist größer > als die vierte wurzel von n
sonst hab ichs gleich

lg spjoe

[Lillipip]

die dritte wurzel von n ist größer > als die vierte wurzel von n
sonst hab ichs gleich

lg spjoe

HA ich wusste ja, dass er mir einen Kaas dazählt, aber er hat mich jetzt ur unsicher gemacht...*hmpf*...

[dog]

Also ich habe in meinen Vorlesungsnotizen stehen, dass
Theta(log2(n)) = Theta(logb(n))

also müßte Theta(log3(n)) = Theta(log4(n))

Laufzeittechnisch gesehen.

[spjoe]

hmm kann seinlog_3(n) = \frac{log_4(n)}{log_4(3) weil dann wäre c ja log_4(3)?

hmm?
lg spjoe

[lowkey]

Ich habe log zur basis 3 gleich log zur basis 4 weil er es in der VO gesagt hat das die basis keine rolle spielt da man es wie eine konstante bewerten kann.

n! < n^n
3. wurzel ist größer als 4. wurzel und 3^n > n^3

[0110]

ich hab mir da einfach excel spalten gemacht und für verschiedene n werte eingesetzt. Weil dann sieht man auch wie sich die Kurven entwickeln, obwohls ja irgendwie eh standardfunktionen sind die jeder von uns schon hundertemal gesehen hat

[Teak]

Die Logarithmen sind auf jeden Fall äquivalent, da die Basis keine Rolle spielt. Der Vergleich von Laufzeiten geschieht nur größenordnungsmäßig - dh. ist es nur wichtig wie sich die Funktionen grundsätzlich entwickeln. Entsprechend sind bei mir auch die beiden Wurzelfunktionen äquivalent - sie entwickeln sich gleich, dass die dritte Wurzel einer Zahl dabei etwas größer ist als die Vierte ist imho nebensächlich.

Lg, Jan

[michaelh]

das mit dem log is klar dass die äquivalent sind, aber 3. und 4. wurzel auch? wäre eine logische schlussfolgerung dass das auch so sein muss, aber wo steht das? hab leider mein skript nicht da

[tonico]

das mit dem log is klar dass die äquivalent sind, aber 3. und 4. wurzel auch? wäre eine logische schlussfolgerung dass das auch so sein muss, aber wo steht das? hab leider mein skript nicht da

Beim log kann man immer eine Konstante finden z.B.

log2n = ϴ(log4n) ⇔ 0 ≤ 2·log4n ≤ log2n ≤ 2·log4n

passt für c1,c2=2 sogar für alle n > 0. Mit Wurzeln geht das eben nicht, denn z.B. für

n1/2 = ϴ(n1/3)
⇔ 0 ≤ c1·n1/3 ≤ n1/2 ≤ c2·n1/3 | : n1/3
⇔ 0 ≤ c1 ≤ n1/2-1/3 ≤ c2

existiert kein passendes c2. Ist das verständlich?

[michaelh]

ja danke, is klar