Apakah O (mn) dianggap pertumbuhan "linear" atau "kuadratik"?

Jika saya memiliki beberapa fungsi yang kompleksitas waktunya adalah O ( mn ), di mana m dan n adalah ukuran dari dua inputnya, apakah kita akan menyebut kompleksitas waktunya "linear" (karena linear pada m dan n ) atau "kuadratik" ( karena ini adalah produk dari dua ukuran)? Atau sesuatu yang lain?

Saya merasa menyebutnya "linear" membingungkan karena O (m + n) juga linear tetapi jauh lebih cepat, tetapi saya merasa seperti menyebutnya "kuadrat" juga aneh karena linear dalam setiap variabel secara terpisah.

Dalam matematika, fungsi seperti ini disebut fungsi multilinear . Tetapi para ilmuwan komputer mungkin umumnya tidak akan tahu terminologi ini. Fungsi ini seharusnya tidak boleh disebut linear, baik dalam matematika atau ilmu komputer, kecuali Anda dapat mempertimbangkan salah satu dari dan n sebagai konstanta.$m$$n$

Untuk menjelaskan diskusi dalam komentar, penting untuk mengukur pertumbuhan Anda.

Seperti disebutkan oleh @Kaveh, tidak linier di keduanya pada saat yang sama, tetapi linier jika yang satu adalah konstanta dan yang lainnya tumbuh.$O(mn)$

Di sisi lain, kemungkinan akan dianggap linier. Secara intuitif, jika m menggandakan, atau jika n menggandakan, atau bahkan jika keduanya m dan n menggandakan, m + n tidak bisa lebih dari dua kali lipat. Hal ini tidak benar dari m n ; jika m dan n keduanya ganda m n naik dengan 4. Inilah sebabnya mengapa dalam banyak konteks waktu berjalan ini akan dianggap kuadratik. Saya memberikan contoh ini dengan pencocokan string dalam beberapa paragraf.$O(m+n)$$m$$n$$m$$n$$m+n$$mn$$m$$n$$mn$

Tetapi biasanya ketika Anda menggunakan notasi Big- , Anda menggunakannya dalam referensi untuk sesuatu yang khusus. Karena kita sebagian besar ahli teori, umumnya ukuran input untuk masalah.$O$

Mari kita ambil Matrix Addition, misalnya. Menambahkan dua matriks membutuhkan O ( m n ) waktu. Tetapi setiap elemen dari input kami hanya disentuh satu kali, jadi ini biasanya akan disebut linear. Dengan kata lain, input kami berukuran O ( m n ) , jadi waktu berjalan O ( m n ) linier dalam ukuran input.$m\times n$$O(mn)$$O(mn)$$O(mn)$

Sekarang mari kita lihat pencocokan string - yaitu, kita diberi string ukuran dan string ukuran n dan kami ingin melihat apakah ada kemunculan string yang lebih kecil di dalam string yang lebih besar. Kita dapat memeriksa ini secara naif dalam waktu O ( m n ) ; ini umumnya dianggap kuadrat. Mengapa? Jika m dan n dapat berupa apa saja, atur m = n . Maka waktu berjalan kami adalah O ( m 2 ) dan input kami berukuran 2 m .$m$$n$$O(mn)$$m$$n$$m = n$$O(m^2)$$2m$

Di sisi lain, jika kita menggunakan algoritma Rabin-Karp , kita mendapatkan (rata-rata) waktu. Input kami terdiri dari kedua string, jadi input kami juga berukuran O ( m + n ) . Oleh karena itu, ini umumnya akan disebut sebagai linear.$O(m+n)$$O(m+n)$

Singkatnya: umumnya disebut linier untuk hal-hal seperti perkalian matriks karena linier dalam ukuran input, tetapi umumnya disebut kuadrat untuk hal-hal seperti pencocokan string karena input yang lebih kecil. Istilah mana yang sesuai tergantung pada konteks Anda menggunakannya.$O(mn)$

Jika Anda mengukur waktu berjalan di maka O ( m n ) adalah tidak fungsi linear di ( m , n ) . Jika tidak ada hubungan antara m dan n fungsi ini dapat tumbuh kuadrat secara umum.$(m,n)$$O(mn)$$(m,n)$$m$$n$

Namun itu adalah fungsi linear di masing-masing secara terpisah, yaitu jika Anda memperbaiki salah satunya dan melihat pertumbuhan dalam variabel lain maka itu adalah fungsi linier pada yang lain.

Untuk mengukur kompleksitas masalah dengan beberapa input , salah satu caranya adalah menemukan variabel dominan dan kemudian mengikat input lain berdasarkan pada variabel tersebut. Dengan pendekatan ini Anda bisa memiliki fungsi kompleksitas berdasarkan pada variabel tunggal .

$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$$\mathcal O(|w_1|\cdot|w_2|)$algoritma yang mengenali sebagai .$L$$\mathcal O(f(|w|)\cdot(|w|-f(|w|))= \mathcal O(f(|w|)|w|-f(|w|)^2)= \mathcal O(f(|w|)|w|)$

$\mathcal O(n\log n)$