Wird O (mn) als "lineares" oder "quadratisches" Wachstum betrachtet?

Wenn ich eine Funktion habe, deren Zeitkomplexität O ( mn ) ist, wobei m und n die Größen der beiden Eingänge sind, würden wir ihre Zeitkomplexität "linear" (da sie sowohl in m als auch in n linear ist ) oder "quadratisch" ( da es ein Produkt von zwei Größen ist)? Oder etwas anderes?

Ich finde es "linear" zu nennen verwirrend, weil O (m + n) ebenfalls linear ist, aber viel schneller, aber ich finde es seltsam, es "quadratisch" zu nennen, weil es in jeder Variablen separat linear ist.

In der Mathematik werden solche Funktionen als mehrlineare Funktionen bezeichnet. Aber Informatiker werden diese Terminologie wahrscheinlich nicht allgemein kennen. Diese Funktion sollte auf jeden Fall nicht linear genannt werden, entweder in der Mathematik oder Informatik, es sei denn , man vernünftigerweise eine von betrachten können und eine Konstante.$m$$n$

Um die Diskussion in den Kommentaren zu erläutern, ist es wichtig, womit Sie das Wachstum messen.

Wie von @Kaveh erwähnt, ist nicht in beiden gleichzeitig linear, sondern ist linear, wenn eine Konstante ist und die andere wächst.$O(mn)$

Andererseits würde wahrscheinlich als linear angesehen. Intuitiv, wenn verdoppelt, oder wenn verdoppelt oder sogar , wenn sowohl und doppelt, kann nicht mehr als verdoppeln. Dies gilt nicht für ; Wenn und beide Doppel- um 4 steigen, wird diese Laufzeit in vielen Zusammenhängen als quadratisch angesehen. Ich gebe ein Beispiel mit String Matching in ein paar Absätzen.m n m n m + n m n m n m $O(m+n)$$m$$n$$m$$n$$m+n$$mn$$m$$n$$mn$

Wenn Sie jedoch die Big- Notation verwenden, verwenden Sie sie in der Regel in Bezug auf eine bestimmte Sache. Da wir meistens Theoretiker sind, ist es im Allgemeinen die Größe des Inputs für das Problem.$O$

Nehmen wir zum Beispiel Matrix Addition. Das Addieren von zwei Matrizen benötigt Zeit. Da jedoch jedes Element unserer Eingabe nur einmal berührt wird, wird dies normalerweise als linear bezeichnet. Mit anderen Worten, unsere Eingabe hat die Größe , sodass eine Laufzeit von in der Größe der Eingabe linear ist.O ( m $m\times n$O ( m n ) O ( m n $O(mn)$$O(mn)$$O(mn)$

Betrachten wir nun die Zeichenfolgenübereinstimmung: Wir erhalten eine Zeichenfolge der Größe und eine Zeichenfolge der Größe und möchten feststellen, ob die kleinere Zeichenfolge in der größeren Zeichenfolge vorkommt. Wir können dies naiv in Zeit überprüfen ; Dies würde im Allgemeinen als quadratisch angesehen. Warum? Wenn und irgendetwas sein können, setze . Dann ist unsere Laufzeit und unsere Eingabe hat die Größe .n O ( m n ) m n m $m$$n$$O(mn)$$m$$n$O ( m 2 ) 2 $m = n$$O(m^2)$$2m$

Wenn wir dagegen den Rabin-Karp-Algorithmus verwenden , erhalten wir (im Durchschnitt) Zeit. Unsere Eingabe bestand aus beiden Zeichenfolgen, daher hatte unsere Eingabe auch die Größe . Daher würde dies allgemein als linear bezeichnet.O ( m + n $O(m+n)$$O(m+n)$

Zusammenfassend lässt sich sagen: wird im Allgemeinen für Dinge wie Matrixmultiplikation als linear bezeichnet, da es in der Größe der Eingabe linear ist, aber im Allgemeinen für Dinge wie String-Matching als quadratisch, da die Eingabe kleiner ist. Welcher Begriff angemessen ist, hängt vom Kontext ab, in dem Sie ihn verwenden.$O(mn)$

Wenn Sie die Laufzeit in messen dann ist nicht eine lineare Funktion in . Wenn es keine Beziehung zwischen und gibt, kann diese Funktion im Allgemeinen quadratisch wachsen .O ( m n ) ( m , n ) m $(m,n)$$O(mn)$$(m,n)$$m$$n$

Es ist jedoch eine lineare Funktion in jedem von ihnen, dh wenn Sie eine von ihnen fixieren und das Wachstum in der anderen Variablen betrachten, dann ist es eine lineare Funktion in der anderen.

Um die Komplexität der Probleme mit mehreren Eingaben zu messen , besteht eine Möglichkeit darin, die dominante Variable zu finden und dann andere Eingaben basierend auf dieser Variablen zu binden. Mit diesem Ansatz könnten Sie die Komplexitätsfunktion auf Basis einer einzelnen Variablen haben .

Gegeben sei eine Sprache und eine Funktion wie Für jedes Sie die Laufzeit eines Algorithmus abschätzen, der als erkennt .f min { | w 1 | , | w 2 | } ≤ f ( | w | ) 2 | ) L O ⋅ ( | w | - f ( | w | ) $L = \{w_1\#w_2|w_i \in (\Sigma\setminus\{\#\})^*,\dots\}$$f$$\min\{|w_1|,|w_2|\} \leq f(|w|)$O ( | w 1 | ⋅ | w ( f ( | w |$w=w_1\#w_2 \in L$$\mathcal O(|w_1|\cdot|w_2|)$$L$$\mathcal O(f(|w|)\cdot(|w|-f(|w|))= \mathcal O(f(|w|)|w|-f(|w|)^2)= \mathcal O(f(|w|)|w|)$

Dies bedeutet, dass Sie eine lineare Zeit erhalten, wenn der kleinere Teil Ihrer Eingabe konstant ist (relativ zur gesamten Eingabe), etwas dazwischen (wie ), wenn sie sublinear ist und eine quadratische Laufzeit, wenn sie linear ist.$\mathcal O(n\log n)$