0 Daumen
336 Aufrufe

Aufgabe:

blob.png



Problem:

Hallu! (。・∀・)ノ゙

kann mir hier vielleicht jemand weiterhelfen? Und zwar würde ich gerne wissen, wie ich sowas auf die schnelle beantworten kann bzw. gleich erkenne ob z.B. f1 in O(f2) liegt und so.

Und könnte vielleicht jemand so freundlich sein und mir die Lösung angeben? Dafür bekommt derjenige auch ewige Dankbarkeit von mir. (づ ̄ 3 ̄)づ

Avatar von

1 Antwort

0 Daumen

Zur Orientierung: für \(m > 1\) gilt

        \(O(1)\subset O(\log n)\subset O(n^{\frac{1}{m}})\subset O(n)\subset O(n\log n)\subset O(n^m) \subset O(2^n)\)

Avatar von 5,6 k

Hm, ich glaube, ich verstehe es nicht ganz. Heißt das einfach, wenn ich zum Beispiel f(n) = 2 log n habe, dann liegt diese Funktion in (n^m), oder?

Ja, es ist tatsächlich \(2 \log n \in O(n^m)\). Außerdem ist auch

        \(2\log n \in O(\log n)\).

Zur Erinnerung:

        \(f\in O(g) \iff \exists N\,\exists c>0\, \forall n\geq N\, |f(n)| \leq c\cdot|g(n)|\).

Dann sieht man \(2\log n \in O(\log n)\) durch Wahl von \(N=1,c=2\).

Oh, so funktioniert das also, ich Danke Dir! (o゜▽゜)o☆

Kannst Du mir vielleicht noch sagen, wie es bei den anderen noch funktioniert, also bei Θ und Ω?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community