Big-O Komplexität von c ^ n + n * (logn) ^ 2 + (10 * N) ^ c
-
25-09-2019 - |
Frage
Ich brauche die Big-O Komplexität dieser Ausdruck abzuleiten:
c ^ n + n * (log (n)) ^ 2 + (10 * N) ^ c
wobei c eine Konstante ist und n eine Variable.
Ich bin sicher, ziemlich Ich verstehe, wie die Big-O Komplexität jedes Begriff individuell abzuleiten, ich weiß nur nicht, wie die Big-O Komplexität ändert sich, wenn die Begriffe wie folgt kombiniert werden.
Ideen?
Jede Hilfe wäre toll, danke.
Lösung
Die O () Notation betrachtet den höchsten Begriff; darüber nachdenken, die man für sehr, sehr große Werte von n
dominieren.
In Ihrem Fall der höchste Begriff ist c^n
, eigentlich, die anderen sind im Wesentlichen Polynom. Also, es ist exponentielle Komplexität.
Andere Tipps
Die Antwort hängt von | c |
Wenn | c | <= 1 Es ist O (n * (log (n)) ^ 2)
Wenn | c | > 1 Es ist O (C ^ n)
In der typischen Nutzung, die formale Definition der O-Notation wird nicht direkt verwendet werden; vielmehr wird die O-Notation für eine Funktion f (x) durch die folgenden Vereinfachungsregeln abgeleitet:
- Wenn f (x) eine Summe von mehreren Bedingungen ist, die mit der größten Wachstumsrate gehalten wird, und alle andere weggelassen.
- Wenn f (x) ein Produkt von mehreren Faktoren ist, werden alle Konstanten (Begriffe in das Produkt, das auf x hängen nicht) entfallen.