Hallo,
gehen wir davon aus, dass eine Funktion f(n) zu der Klasse O( g(n) ) gehört. Dann gilt ab einem bestimmten n0:
f(n) = n0
Also ab einem bestimmten Glied sind alle Folgenglieder von f kleiner als ein Vielfaches der Funktion g. Dabei ist k eine beliebige aber feste reelle Zahl.
Betrachten wir f(n) = 2 * n^2 + n + 1 und g(n) = n
Egal, wie groß k gewählt wird, irgendwann werden die Folgenglieder von f wieder größer als g. Also ist f nicht in der Klasse O(n).
Betrachten wir die gleiche Funktion f und die Funktion g(n) = n^2.
Dann können wir zum Beispiel k = 3 wählen. Die ersten Glieder von f wären dann 1, 4, 11, 22. Die von 3*g sind 0, 3, 12, 48.
Ab dem zweiten Glied ist 3*g also immer größer als f. Somit liegt f in O(n^2).
Wie kommt man jetzt auf die Klassen? Eines haben wir ja schon gesehen. Quadratische Funktionen lassen sich nicht durch lineare Funktionen abschätzen. Das heißt also, in der beschränkenden Funktion steht i.A. immer auch die höchste Potenz von n. Alle niedrigeren Potenzen fallen weg, da sie durch den konstanten Faktor abgedeckt werden können. Mit steigendem n fallen die niedrigeren Potenzen also immer weniger ins Gewicht.
Oft spielen auch Funktionen wie der Logarithmus eine Rolle. Diese bleiben auch in der beschränkenden Funktion erhalten. Konstante Faktoren fallen natürlich hier wieder weg. So kommt man auf die oft verwendete Klasse O(n log n). Die Basis des Logarithmus spielt keine Rolle, da Logarithmen zu unterschiedlichen Basen ja auch nur Vielfache voneinander sind.
Ich denke, damit solltest du das meiste ganz gut lösen können.
Nico
