O-Notation

26.03.2011, 20:08	plizzz	Auf diesen Beitrag antworten »
O-Notation Hallo, ich habe einen Graphen mit n Knoten und m Kanten und zwei Algorithmen, die die folgenden Laufzeiten haben: $\begin{eqnarray} 1) \Theta ((m \cdot log(m)) \cdot (m + n \cdot log(n))) \end{eqnarray}$ $\begin{eqnarray} 2) \Theta ((m \cdot log(m)) \cdot (n^2 \cdot log(m))) \end{eqnarray}$ Es gilt immer n= O(m) und meine Aufgabe ist es, herauszufinden, ab welchem Verhältnis von n und m (in O-Notation) welcher Algorithmus besser ist. Ich hätte dann gerne so eine Aussage wie: Für $\begin{eqnarray} n=o(f(m)) \end{eqnarray}$ ist 2) besser, für $\begin{eqnarray} n= \Omega (f(m)) \end{eqnarray}$ ist 1) besser. Irgendwie sind solche Aussagen mit der O-Notation gar nicht so einfach. Gibt es da ein festes Rezept? Den linken Faktor habe ich bei meinem Vergleich weggelassen, da er bei beiden Termen gleich ist, und habe erstmal nur die beiden rechten Terme verglichen. Dann habe ich erstmal einfach $\begin{eqnarray} n = \Theta (m^k), \ 0<k \leq 1 \end{eqnarray}$ gesetzt und bin zum Ergebnis gekommen, dass ich es für diesen Fall für festes k entscheiden kann: Für 0 < k < 1/2 ist Algorithmus 2) besser, für 1/2 <= k <= 1 ist Algorithmus 1) besser. Ich war dann schnell versucht, obige Aussage mit $\begin{eqnarray} f(m)= m^{1/2} \end{eqnarray}$ , aber ich glaube nicht, dass das stimmt. Schließlich gibt es ja Funktionen, die asymptotisch schwächer in m als m^(1/2) aber stärker als m^k für k<= 1/2 wachsen, zB f(m)= m^(1/2) * (1/log(m)). Irgendwie kann man da jetzt aber beliebig lange rumfummeln und wenn die Ausdrücke etwas komplizierter werden (muss das noch mit einer Reihe von Algorithmen machen), dann wirds wohl düster. Jemand eine Idee? MfG plizzz
26.03.2011, 21:24	plizzz	Auf diesen Beitrag antworten »
Ok, ich bin gerade selbst drauf gekommen, glaube ich. Ich habe $\begin{eqnarray} n= \Theta ( (m/log(m))^{1/2} ) \end{eqnarray}$ gesetzt. Dann sind beide Ausdrücke asymptotisch gleich und da sie unterschiedlich stark in n wachsen, dürfte es klar sein. Mal sehen, ob diese Methode auch sonst klappt (oder kennt jemand eine bessere ?). MfG plizzz

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »