Kann eine Big-Oh-Zeitkomplexität mehr als eine Variable enthalten?

Nehmen wir zum Beispiel an, ich mache eine String-Verarbeitung, die eine Analyse von zwei Strings erfordert. Ich habe keine Informationen darüber gegeben, wie lang sie sein könnten, daher stammen sie aus zwei verschiedenen Familien. Wäre es akzeptabel, die Komplexität eines Algorithmus oder (je nachdem, ob wir einen naiven oder einen optimierten Algorithmus verwenden)?O ( n + m $O(n * m)$$O(n + m)$

Nehmen wir in ähnlicher Weise an, dass der von uns gewählte Algorithmus tatsächlich zwei Stufen erfordert - eine Einrichtungsphase für die erste Zeichenfolge, mit der wir eine beliebige Anzahl anderer Zeichenfolgen verarbeiten können, ohne dass diese anfänglichen Kosten anfallen. Wäre es angemessen zu sagen, dass es eine -Konstruktion hat, gefolgt von einer beliebigen Anzahl von -Berechnungen?O ( m $O(n)$$O(m)$

Wäre es angebracht, sie einfach da beide Berechnungen linear sind?$O(n)$

Ja natürlich. Das ist in Ordnung und vollkommen akzeptabel. Es ist üblich und Standard, Algorithmen zu sehen, deren Laufzeit von zwei Parametern abhängt.

Beispielsweise wird häufig die Laufzeit der Tiefensuche als ausgedrückt , wobei die Anzahl der Scheitelpunkte und die Anzahl der Kanten im Diagramm ist. Dies ist vollkommen gültig. Die Bedeutung davon ist, dass es eine Konstante und Zahlen so dass die Laufzeit des Algorithmus höchstens für alle . Mit anderen Worten, wenn die genaue Laufzeit , sagen wir, dass wenn existiert so dass und impliziert$O(n+m)$$n$$m$$c$$n_0,m_0$$c \cdot (n+m)$$n>n_0,m>m_0$$f(n,m)$$f(n,m) = O(n+m)$$c,n_0,m_0$$n>n_0$ f ( n , m ) ≤ c ⋅ ( n + m $m>m_0$$f(n,m) \le c \cdot (n+m)$ .

Ja, es ist vollkommen angemessen und akzeptabel zu sagen, dass die erste Stufe Zeit und die zweite Stufe Zeit benötigt.O ( m $O(n)$$O(m)$

Wichtig: Stellen Sie sicher, dass Sie definieren, was und sind. Sie können nicht sagen, dass dies ein -Zeitalgorithmus ist, ohne anzugeben, was ist. Wenn in der Problemstellung nicht angegeben ist, müssen Sie es angeben. Siehe zum Beispiel Diagrammalgorithmen, in denen wir normalerweise Anzahl der Eckpunkte und Anzahl der Kanten definieren.m O ( n ) n n n = m $n$$m$$O(n)$$n$$n$$n =$$m =$

Was die Frage betrifft, ob Sie sie -Zeit nennen können , nein, natürlich nicht - es sei denn, Sie wissen irgendwie, dass . Wenn Sie wissen, dass , folgt natürlich , sodass ein -Zeitalgorithmus auch ein -Zeitalgorithmus ist. Wenn es jedoch keine Garantie dafür gibt, dass , können Sie es nicht als -Zeitalgorithmus bezeichnen.m = O ( n $O(n)$$m = O(n)$m + n = O ( n ) O ( m + n ) O ( n ) m = O ( n ) O ( n $m = O(n)$$m+n = O(n)$$O(m+n)$$O(n)$$m = O(n)$$O(n)$

Das ist grundlegendes Zeug. Sie finden es überall in Lehrbüchern für Algorithmen.