Forum aufgabe Definition Informatik C1 C2

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

Von: , Frage gestellt am Di, 22. Nov 2005

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 ;-)

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 ! ;)

Ich vermute, dass man über die Zeile

g(n) <= c* f(n) gehen muss?

Aber was macht man dann damit?

Und muss man da vielleicht dieses c1*n+c2 einsetzen?

Danke
Daria

3 Antworten zu dieser Frage

1. Antwort von nach 9 Stunden 0 hilfreich

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

   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(c) = 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 ;-)
   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) <= c* f(n) gehen muss?
   Jo, sieht gut aus. Und muss man da vielleicht dieses c1*n+c2 einsetzen?
   g(x + y) = f(x) + f(y) ??
   
   cu
   

   • Antwort von nach 11 Stunden 0 hilfreich

     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?
     

     • Antwort von nach 2 Tagen 0 hilfreich

       Re: Hab mir mal was überlegt

       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 <= statt >= 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) <= c*(c1*n+c2) = c*c1*n+c*c2 = c1'*n + c2'
       c1'*n + c2' <= c1'*n + c2'*n = (c1' + c2') * n = c' * n
       Daraus folgt dann, dass O(c1*n+c2) = O(n) ist.
       
       Sebastian.
       

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!