Kurs:Algorithmen und Datenstrukturen/Vorlesung/Notation Eigenschaften

Aus Wikiversity




Lemma[Bearbeiten]

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]

Lemma[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

Lemma[Bearbeiten]

Falls , dann ist auch . 

Beweis[Bearbeiten]

Dabei ist eine Konstante.

Beispiel[Bearbeiten]

Lemma[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.

Lemma[Bearbeiten]

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


Discussion