Effizienz
Komplexitätsvergleich zweier Algorithmen
In diesem Abschnitt wollen wir der Frage nachgehen, wie ein formaler Beweis für die Behauptung <math> f(N) \in \mathcal{O}(g(N)) </math> geschehen kann. Hierbei werden zwei Beweismethoden vorgestellt werden, und zwar der Beweis über die Definition der Komplexität sowie der Beweis durch Dividieren.
Beweis über die Definition der asymptotischen Komplexität
Die Definition der asymptotischen Komplexität <math>f(N) \in \mathcal{O}(g(N))</math> war:
Es gibt eine Konstante <math> c > 0 </math>, so dass <math> f(N) \le c \cdot g(N) </math> für <math> N \ge N_0 </math> erfüllt ist.
Um also die die asymptotische Komplexität <math>f(N) \in \mathcal{O}(g(N))</math> zu beweisen, muss man die oben erwähnten Konstanten c und <math> N_0 </math> finden, so dass
<math> f(N) \leq g(N) </math>
für alle <math> N \ge N_0 </math> erfüllt ist. Dies geschieht zweckmäßigerweise mit dem Beweisprinzip der vollständigen Induktion. Hierbei ist zu zeigen, dass
- <math> f(N_0) \leq g(N_0) </math> für die eine zu bestimmende Konstante <math> N_0 </math> gilt (Induktionsanfang) und
- falls <math> f(N) \leq g(N) </math> gilt, dann auch <math> f(N+1) \leq g(N+1) </math> (Induktionsschritt) gilt.
Beweis durch Dividieren
Hierbei wählt man eine Konstante c und zeigt, dass <math> \lim_{N \rightarrow \infty} \frac{f(N)}{c \cdot g(N)} \leq 1 </math> gilt. Als Beispiel betrachten wir die beiden Funktionen <math> f(N) = N \lg N </math> und <math> g(N) = N^2 </math> und wollen zeigen, dass <math>f(N) \in \mathcal{O}(g(N))</math> gilt. Als Konstante c wählen wir <math> c = 1 </math>.
<math> \lim_{N \rightarrow \infty} \frac{f(N)}{g(N)} = \lim_{N \rightarrow \infty} \frac{\lg N}{N} = \frac{\infty}{\infty} </math>
Unbestimmte Ausdrücke der Form <math> \lim_{x \rightarrow x_0} \frac{f(x)}{g(x)} </math>, in denen sowohl <math> f(x) </math> als auch <math> g(x) </math> mit <math> x \rightarrow x_0 </math> gegen Null oder gegen Unendlich streben, kann man manchmal mit den Regeln von l'Hospital berechnen. Danach darf man die Funktionen f und g zur Berechnung des unbestimmten Ausdrucks durch ihre k-ten Ableitungen ersetzen:
<math> \lim_{x \rightarrow x_0} \frac{f(x)}{g(x)} = \lim_{x \rightarrow x_0} \frac{f^{(k)}(x)}{g^{(k)}(x)} </math>
In unserem Fall verwenden wir die erste Ableitung und erhalten: <math> \lim_{N \rightarrow \infty} \frac{f'(x)}{g'(x)} = \lim_{N \rightarrow \infty} \frac{1/N}{1} \rightarrow 0 </math>
Damit wurde <math>f(N) \in \mathcal{O}(g(N))</math>, also <math>N \lg N \in \mathcal{O}(N^2)</math> gezeigt. Man beachte hierbei, dass <math>N \lg N \in \mathcal{O}(N^2)</math> keine enge Grenze für die Komplexität von <math>N \lg N)</math> darstellt, da der Grenzwert <math> \lim_{N \rightarrow \infty} \frac{f'(x)}{g'(x)} </math> gegen 0 und nicht gegen eine von Null verschiedene Konstante strebt. In diesem Fall haben wir also die Komplexität von <math>N \cdot \lg N </math> nur nach oben abschätzen können.
