Können Sie die asymptotisch beschriebenen Funktionen bearbeiten und daraus Schlussfolgerungen ziehen?

Diese Frage basiert auf Hausaufgaben (ohne das eigentliche Problem zu verwenden)!

Angenommen, Sie haben eine Funktion, die wie folgt beschrieben wird:

Können Sie dann Folgendes behandeln:

und führt Mathematik darauf und behält seine asymptotische Bedeutung?

Könnte ich im obigen Fall vermuten, dass impliziert (unter der Annahme, dass Koeffizienten in diesem Beispiel eine Rolle spielen)?$f(n) \in O(2n^2)$$f(n) / 2 \in O(n^2)$

Bei einigen Operationen, wie z. B. Addition, Multiplikation, können Sie die asymptotische Notation direkt bearbeiten. Wenn zum Beispiel und , dann und . Für einige andere Operationen, wie zum Beispiel die Division, kommt es dann darauf an. Zum Beispiel ist es für und nicht richtig, zu sagen (betrachte und ). Wenn jedoch eine feste Konstante ist, dann$\small g(n) = \mathcal{O}(n^2)$$\small f(n) = \mathcal{O}(n^2)$$\small g(n) + f(n) = \mathcal{O}(n^2)$$\small g(n) \cdot f(n) = \mathcal{O}(n^4)$$\small g(n) = \mathcal{O}(n^2)$$\small f(n) = \mathcal{O}(n^2)$$\small \frac{g(n)}{f(n)} = \mathcal{O}(1)$$\small g(n) = n^2$$\small f(n) = n$$c$$\small \frac{g(n)}{c} = \mathcal{O}(n^2)$ .

Verwenden Sie die Definition von, um Fragen wie Ihre Vermutung zu beantworten $O$. Paraphrasierung aus Wikipedia zum Zeitpunkt des Schreibens:

$f \in O(g)$ iff $f(x) \leq M\times g(x)$ für alle $x > x_0$für einige Konstanten $M$ und $x_0$.

Also wenn $f(n) \in O(2n^2)$, dann $f(n) \leq C \times 2n^2 \ \ \forall n > n_0$ für einige Konstanten $C$ und $n_0$ (Ich nenne es $C$ anstatt $M$um später Verwirrung zu vermeiden). Sie werden feststellen, dass wir das kombinieren können$2C$ in eine Konstante, die Ihnen sagt $O(2n^2) = O(n^2)$.

Was können wir dazu sagen? $f(n)/2$? Wir können jetzt die normale Algebra für die Ungleichung verwenden, z. B. beide Seiten durch 2 teilen, um Folgendes zu erhalten:

$f(n)/2 \leq Cn^2 \ \ \forall n > n_0$

Ist das noch $O(n^2)$? Um dies zu überprüfen, müssen wir Konstanten finden$M$ und $x_0$so dass die obige Definition gilt. In diesem Fall,$M = C$ und $x_0 = n_0$funktioniert. Beachte das$M = 327.6C$ist auch gültig; Sie können jede beliebige Methode verwenden, um diese Konstanten zu finden, solange Sie wissen, dass sie konstant sind.

In der realen Welt werden Sie in der Lage sein, das meiste davon zu "verkürzen", wenn Sie Ihre Analyse durchführen, wie es NP-hard in seiner Antwort tut, aber dies sind nur Abkürzungen, um es so rigoros zu schreiben (was ich erwarten würde) Hausaufgaben speziell über$O$). Wenn Sie nicht sicher sind, ob es gültig ist, holen Sie sich das$O$Verwenden Sie die Definition, führen Sie eine Algebra für die Ungleichung durch und bringen Sie sie dann wieder ein $O$ indem Sie die geeigneten Konstanten finden (oder einfach zeigen, dass sie existieren).