Czy O (mn) jest uważany za wzrost „liniowy” czy „kwadratowy”?

Jeśli mam jakąś funkcję, której złożoność czasowa wynosi O ( mn ), gdzie m i n są wielkościami jej dwóch danych wejściowych, nazwalibyśmy jej złożoność czasową „liniową” (ponieważ jest liniowa zarówno m, jak i n ) lub „kwadratową” ( ponieważ jest to produkt dwóch rozmiarów)? Albo coś innego?

Czuję, że nazywanie go „liniowym” jest mylące, ponieważ O (m + n) jest również liniowe, ale znacznie szybsze, ale mam wrażenie, że nazwanie go „kwadratowym” jest również dziwne, ponieważ jest liniowe w każdej zmiennej osobno.

W matematyce takie funkcje nazywane są funkcjami wieloliniowymi . Ale informatycy prawdopodobnie na ogół nie znają tej terminologii. Funkcja ta powinna zdecydowanie nie można nazwać liniowy, albo w matematyce i informatyce, chyba że można rozsądnie rozważyć jeden z i n stałą.$m$$n$

Aby wyjaśnić dyskusję w komentarzach, ma znaczenie to, co mierzysz w odniesieniu do wzrostu.

Jak wspomniano @Kaveh, nie jest liniowe w obu w tym samym czasie, ale jest liniowe, jeśli jeden jest stały, a drugi rośnie.$O(mn)$

Z drugiej strony prawdopodobnie można by uznać za liniowe. Intuicyjnie, jeśli m podwaja się lub n podwaja się, a nawet jeśli oba m i n podwajają się, m + n nie może więcej niż podwoić. Nie jest to prawdziwe w odniesieniu do m n ; jeśli zarówno m, jak i n, podwójnie $O(m+n)$$m$$n$$m$$n$$m+n$$mn$$m$$n$ idzie się przez 4. To dlatego w wielu kontekstach, tym razem z systemem byłoby uznane kwadratowa. Podam przykład tego z dopasowaniem łańcucha w kilku akapitach.$mn$

Ale zwykle, gdy używasz Big- $O$ notacji , używasz jej w odniesieniu do czegoś konkretnego. Ponieważ jesteśmy głównie teoretykami, zazwyczaj jest to wielkość wkładu w problem.

Weźmy na przykład dodatek macierzy. Dodanie dwóch macierzy zajmuje czas O ( m n ) . Ale każdy element naszego wkładu jest dotykany tylko raz, więc zwykle nazywa się to liniowym. Innymi słowy, nasze dane wejściowe mają rozmiar O ( m n ) , więc czas działania O ( m n $m\times n$$O(mn)$$O(mn)$$O(mn)$ jest liniowy pod względem wielkości danych wejściowych.

Teraz spójrzmy na dopasowanie łańcucha - mianowicie, otrzymujemy łańcuch o rozmiarze i łańcuch o rozmiarze n i chcemy sprawdzić, czy występuje wystąpienie mniejszego ciągu w większym ciągu. Możemy to naiwnie sprawdzić w czasie O ( m n ) ; byłoby to ogólnie uważane za kwadratowe. Czemu? Jeśli m i n mogą być czymkolwiek, ustaw m = n . Zatem nasz czas pracy wynosi O ( m 2 ), a nasze dane wejściowe mają rozmiar 2 m .$m$$n$$O(mn)$$m$$n$$m = n$$O(m^2)$$2m$

Z drugiej strony, jeśli użyjemy algorytmu Rabin-Karp , otrzymamy (średnio) czas . Nasze dane wejściowe składały się z obu ciągów, więc nasze dane wejściowe również miały rozmiar O ( m + n ) . W związku z tym byłoby to ogólnie określane jako liniowe.$O(m+n)$$O(m+n)$

Podsumowując: jest ogólnie nazywane liniowym dla rzeczy takich jak mnożenie macierzy, ponieważ jest liniowy w wielkości danych wejściowych, ale jest ogólnie nazywany kwadratowy dla rzeczy takich jak dopasowanie łańcucha ze względu na mniejsze dane wejściowe. To, który termin jest odpowiedni, zależy od kontekstu, w którym go używasz.$O(mn)$

Jeśli pomiar czasu pracy w następnie O ( m n ) to nie funkcja liniowa ( m , n ) . Jeżeli nie ma żadnej zależności od m i n to funkcja może wzrastać quadraticly w ogóle.$(m,n)$$O(mn)$$(m,n)$$m$$n$

Jest to jednak funkcja liniowa w każdym z nich osobno, tzn. Jeśli naprawisz jedną z nich i spojrzysz na wzrost w drugiej zmiennej, to będzie to funkcja liniowa w drugiej.

Aby zmierzyć złożoność problemów z wieloma danymi wejściowymi , jednym ze sposobów jest znalezienie zmiennej dominującej , a następnie powiązanie innych danych wejściowych na podstawie tej zmiennej. Dzięki takiemu podejściu możesz mieć funkcję złożoności opartą na pojedynczej zmiennej .

Biorąc pod uwagę język i funkcja f taka, że min { | w 1 | , | w 2 | } ≤ f ( | w | ) dla każdego w = w 1 # w 2 ∈ $L = \{w_1\#w_2|w_i \in (\Sigma\setminus\{\#\})^*,\dots\}$$f$$\min\{|w_1|,|w_2|\} \leq f(|w|)$$w=w_1\#w_2 \in L$możesz oszacować czas działania algorytmu , który rozpoznaje L jako O ( f ( | w | ) ⋅ ( | w | - f ( | w | ) ) = O ( f ( | w | ) | w | - f ( | w | $\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|)$

Oznacza to, że otrzymujesz czas liniowy, jeśli mniejsza część danych wejściowych jest stała (w stosunku do całości danych wejściowych), coś pomiędzy (jak ), jeśli jest sublinearny i kwadratowy, jeśli jest liniowy.$\mathcal O(n\log n)$