Kurs:Algorithmen und Datenstrukturen/Vorlesung/Notation Eigenschaften




Für beliebige Funktionen f,g gilt:
 

Beweis in beide Richtungen

Bearbeiten

 

 

Als erstes machen wir den Beweis nach rechts ( )

 

 

 

nun der Beweis nach links ( )

 

 

 

Beispiel

Bearbeiten

 

 

 

1.  
2.  
3.  


Beweis in beide Richtungen

Bearbeiten

Beweis zu 1. nach rechts ( )

 

 


Beweis zu 1. nach links ( )

 

  (siehe Definition)


und sei t(n) ein beliebiges Element der Menge O(f(n))


  (siehe Definition)

 

 

  (Definition der Teilmenge, da t(n) ein beliebiges Element ist)

Beispiele

Bearbeiten

 


Damit ist

 

 

 


Damit ist

 

 


Damit ist

 

Falls  , dann ist auch  . 

 

 

 

Dabei ist   eine Konstante.

Beispiel

Bearbeiten

 

 

 

 

1.  
2.  

Ein häufiges Problem sind Grenzwerte der Art   oder   Bei diesem Problem kann man als Ansatz die Regel von de l'Hospital verwenden.

Satz(Regel von de L'Hospital)  
Seien f und g auf dem Intervall   differenzierbar.
Es gelte   
und es existiere  .
Dann existiert auch   und es gilt:
 

Beispiel

Bearbeiten

1.  

 

2.  

 

Beim zweiten Beispiel musste die Regel von de l'Hospital wiederholt angewandt werden.

Gibt es immer eine Ordnung zwischen den Funktionen? Es gibt Funktionen f und g mit  . Ein Beispiel sind die Funktionen sin(n) und cos(n).

Für alle  

Beweis durch Widerspruch

Bearbeiten

Wir nehmen an, dass  ,

das heißt  .

Aber es muss auch   gelten,

das heißt