Mathe / Informatik (Algorithmik, Landau etc)

[Eeth]

Hi,
verzweifle gerade an den ziemlichen basic sachen der algorithmik.

folgende aufgaben sind gegeben:

Problem 1: Asymptotic Notations (Die ')' soll auch eine echte Teilmenge darstellen in der Aufgabenstellung )

Compare the following sets ( ')' , C, =) and prove your statements.
(a) O(n^2) and O(n log n)
(b) Theta(2^n) and Theta(n^n)
(c) o(2^n) and o(2^(n+1))

Problem 2: Asympotically Tight Bound 3
Let f and g be two nonnegative functions. Prove that
max(f(n), g(n)) Element O(f(n) + g(n)).

1. wie führe ich beweis in aufgabe 1?
2. was soll das max? WIe löse ich das?


danke!

 

[Asta Khan_inaktiv]

Für die Inklusionen: Schau dir die Definitionen von den Notationen an, nimm ein Element aus der einen Menge und zeige es liegt in der anderen Menge?

Und bei der zweiten musst du halt bloß die Definition von O einsetzen. Das Maximum ist halt die Funktion, die an der Stelle n grade den größeren der Werte f(n) und g(n) hat, d.h. es ist kleiner gleich f+g (weil f, g nicht negativ).

 

[Amad3us]

max(f(n),g(n))<=f(n)+g(n)

--> max(f(n),g(n)) / (f(n)+g(n)) <= (f(n)+g(n))/(f(n)+g(n))=1

Damit ist der Grenzwert jeder Folge für n --> unendlich beschränkt

--> O()-Formel

 

[Amad3us]

Zu 1 habe ich nur eine Vermutung:

Sei f(n)=O(n*log(n)) --> für n --> unendlich ist f(n)/(n*log(n)) <= Konstante

--> für n --> unendlich ist f(n)/n^2 <= f(n)/(n*log(n)) <=Konstante

d.h. aus f(n)=O(n*log(n)) folgt f(n)=O(n^2)