Was ist das große O von T (n)?

Ich habe eine Hausaufgabe, bei der ich die Formel und die Reihenfolge von die durch gegeben ist $T(n)$

T (1) = 1 T (n) = \frac{T (n - 1)}{T (n - 1) + 1} .

$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.$

Ich habe festgestellt, dass aber jetzt bin ich ein wenig verwirrt. Ist die richtige Antwort für den zweiten Teil? $T(n) = \frac{1}{n}$ $T(n) \in O(\frac{1}{n})$

Basierend auf der Definition von Big-O haben wir das

O (g (n)) = {f (n) ∣ \exists c, n_{0} > 0 s.t. 0 \leq f (n) \leq c g (n) for all n \geq n_{0}} .

$O(g(n)) = \{f(n) \mid \exists c, n_0>0\text{ s.t. } 0\leq f(n) \leq cg(n)\text{ for all } n\geq n_0\}\,.$

Dies gilt für . Basierend auf der Definition sollte korrekt sein, aber in der realen Welt ist dies unmöglich Dieser Algorithmus kann schneller als . $f(n) = g(n) = \frac{1}{n}$ $O(\frac{1}{n})$ $O(1)$

algorithm-analysis asymptotics recurrence-relation Karo
quelle

Antworten:

Ja, alle Funktionen erfüllen . Die Definitionen sind auch dann sinnvoll, wenn nicht die Laufzeit einer Funktion ist. In der Tat stammt diese Notation aus der Zahlentheorie, wobei normalerweise ein Fehlerterm ist. Selbst in der Informatik werden manchmal große O-Notationen verwendet, wenn Algorithmen auf etwas anderes als Laufzeit- oder Platzanforderungen analysiert werden. $f(n)$ $f(n) \in O(f(n))$ $f(n)$ $f(n)$

Yuval Filmus
quelle

Es sieht so aus, als ob der Unterschied darin besteht, dass mit wächst, wenn zunimmt, aber die Anzahl der Operationen zur Berechnung von ist wenn Sie zu vereinfachen oder wenn Sie die im Hausaufgabenproblem angegebene Definition direkt verwenden.

T (n)

$T(n)$

\frac{1}{n}

$\frac{1}{n}$

n

$n$

T (n)

$T(n)$

O (1)

$O(1)$

T (n)

$T(n)$

T (n) = \frac{1}{n}

$T(n) = \frac{1}{n}$

O (n^{2})

$O(n^2)$

Kevin

@ Kevin Die Frage sagt überhaupt nichts über die Anzahl der Operationen aus, die erforderlich sind, um etwas zu berechnen: Sie fragt nur nach der Lösung für eine Wiederholungsbeziehung. Lösungen für Wiederholungen müssen keine Laufzeiten für Algorithmen sein, genauso wie Zahlen keine Längen oder Gewichte sein müssen.

David Richerby