O-Notation, Beweis - wie setzt man da an?

Wissenschaft Informatik
#1

Hallo!

Ja, cih weiß, dass das Forum hier nicht zum „Hausaufgabenmachen“ gedacht ist, aber ich habe jetzt schon so lange über der Aufgabe gegrübelt und Google bemüht und in verschiedenen Informatik-Büchern nachgeschlagen, dass mir als letzte Möglichkeit dieses Forum hier eingefallen ist, direkt mal jemanden zu fragen, der sich damit auskennt.

Es geht um die O-Notation.

Und zwar sollen wir beweisen, dass

O(c1*n+c2) = O(n) ist, mithilfe der Definition der Ordnungsklassen.
c1 und c2 sind beliebige aber feste positive relle Zahlen.

Die Definition ist ja eine lange geschweifte Klammer mit O(f) = {g: …} (die ich endlcih auch in groben Zügen verstanden hab :wink:

Das Problem ist nur: Überall steht einfach „Konstanten fallen weg / werden eliminiert…“ aber das wird immer als tatsache hingestellt und nicht bewiesen, hab zumindest noch nichts dazu gefunden.

Ich hätte gerne einen Denkansatz, dann wär ich schon glücklich ! :wink:

Ich vermute, dass man über die Zeile

g(n)

#2

Moien

Es geht um die O-Notation.

Bei der jeder Prof seine eigenen Vorstellungen hat.

O(c1*n+c2) = O(n) ist, mithilfe der Definition der
Ordnungsklassen.

Gibts da zufälligerweise die Definitionen:

O© = O(1)
O(c*n) = O(n)

In dem Fall wär er an dem Skript aus meiner Unizeit dran.

Die Definition ist ja eine lange geschweifte Klammer mit O(f)
= {g: …} (die ich endlcih auch in groben Zügen verstanden
hab :wink:

Klasse, die hatten wir nicht…

Das Problem ist nur: Überall steht einfach „Konstanten fallen
weg / werden eliminiert…“ aber das wird immer als tatsache
hingestellt und nicht bewiesen, hab zumindest noch nichts dazu
gefunden.

Tatsachen und Axiome werden nicht bewiesen, die gelten einfach so. Man kann die Grundlage einer Theorie nicht mit Hilfe der Theorie beweisen. Da beisst sich die Katze in den Schwanz…

Ich vermute, dass man über die Zeile

g(n)

#3

Hab mir mal was überlegt
Aber ich hab null Ahnung ob das richtig ist, bzw ob man das so machen kann…

Also:

O(c1*n+c2) = O(n)

Es gilt für n>0

g(n) >= c*f(n)

c1*n + c2 >= (c1 + c2) * n // hab c = c1+c2 gesetzt (darf man das?)

c1*n + c2 >= c1 * n + c2* n

irgendwie etwas ZU simpel…
aber ich würd dann einfach sagen, dass diese Ungleichung wahr ist und daher auch die zu beweisende Aussage oben wahr ist.

Mmmh, was meint ihr?

#4

Hallo

Aber ich hab null Ahnung ob das richtig ist, bzw ob man das so
machen kann…

Also:

O(c1*n+c2) = O(n)

Es gilt für n>0

g(n) >= c*f(n)

c1*n + c2 >= (c1 + c2) * n // hab c = c1+c2 gesetzt (darf
man das?)

Ja, das darf man. Du kannst dir ein beliebiges c aussuchen, also auch c=c1+c2. Aber wenn mich nicht alles täuscht, müsste da jeweils = stehen.
Dann hättest du nämlich gezeigt, dass c1*n+c2 „nicht schneller wächst als“ n und deswegen O(n) ist.
Hm, achso, um genau zu sein, hat man damit gezeigt, dass c1*n+c2 = O(n) ist. Um O(c1*n+c2) = O(n) zu zeigen, könnte man folgendes machen:

Es gibt eine Funktion f(n), die sich durch O(c1*n+c2) abschätzen lässt, daher:
f(n)