Apa arti dari

$O(m+n)$ $O(\max(m,n))$ $O(\min(m,n))$ $O(|V| + |E|)$

terminology asymptotics mathematical-analysis landau-notation jujur
sumber

mungkin tergantung pada

m

$m$

n

$n$

Andrew

Jawaban:

Kamu benar. Perhatikan bahwa istilah sedikit menyalahgunakan Notasi besar-O klasik , yang didefinisikan untuk fungsi dalam satu variabel. Namun ada ekstensi alami untuk beberapa variabel. $O(n+m)$

Secara sederhana, karena Anda dapat menyimpulkan bahwa dan setara dengan batas atas asimptotik.

\frac{1}{2} (m + n) \leq max {m, n} \leq m + n \leq 2 max {m, n},

$\frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$

O (n + m)

$O(n+m)$

O (max {m, n})

$O(\max\{m,n\})$

Di sisi lain berbeda dari , karena jika Anda mengatur , Anda mendapatkan $O(n+m)$ $O(\min\{n,m\})$ $n=2^m$

O (2^{m} + m) = O (2^{m}) ⊋ O (m) = O (min {2^{m}, m}) .

$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$

A.Schulz
sumber

Saya pikir patut dicatat bahwa mereka menulis dalam abstrak, "Kami menunjukkan bahwa tidak mungkin untuk mendefinisikan notasi O besar untuk fungsi pada lebih dari satu variabel dengan cara yang menyiratkan properti yang biasa digunakan dalam analisis algoritma. Kami juga menunjukkan bahwa definisi umum jangan menyiratkan sifat-sifat ini bahkan jika fungsi-fungsi dalam notasi-O besar dibatasi hanya untuk tidak meningkatkan "

Raphael

Sebagai tindak lanjut dari komentar saya di atas, artikel terbaru Definisi umum notasi-O untuk analisis algoritma oleh K. Rutanen (2015) memang menunjukkan bagaimana mendefinisikan notasi-O yang bermakna untuk set umum, termasuk .

N^{2}

$\mathbb{N}^2$

Raphael

Percaya atau tidak, tampaknya (dalam pengalaman saya) bahwa banyak algoritma orang sebenarnya tidak memikirkan apa arti notasi O besar secara formal, dan ketika ditanya tentang hal itu, Anda bisa mendapatkan beberapa jawaban berbeda. Beberapa masalah dibahas dalam makalah On Asymptotic Notation with Multiple Variables oleh Rodney R. Howell.

Anehnya, tampaknya juga sebagian besar kursus algoritma pengantar menghabiskan banyak waktu menjadi sangat formal tentang notasi O besar dengan variabel tunggal, dan kemudian minggu-minggu berikutnya dengan senang hati menggunakan notasi untuk algoritma grafik dengan beberapa variabel dengan cara biasa, tanpa membahas apa notasi sebenarnya berarti.

Kristoffer Arnsfelt Hansen
sumber

Tautan dalam jawaban saya merujuk pada artikel Howell, yang memang merupakan perlakuan yang bagus untuk pertanyaan ini.

A.Schulz

@ A.Schulz: Memang, saya mengetik jawaban saya secara bersamaan kepada Anda.

Kristoffer Arnsfelt Hansen

Saya seorang pendukung untuk berhati-hati dengan ketentuan-ketentuan Landau jadi saya setuju, tetapi ini mengandung terlalu banyak kata-kata kasar untuk jawaban yang baik.

Raphael

@ Raphael: Jawabannya tidak dimaksudkan sebagai kata-kata kasar, tapi mungkin bisa diucapkan lebih tepat. Masalahnya, pertanyaannya adalah pada dasarnya, apa arti big O dengan lebih dari satu parameter. Jawabannya adalah, itu harus berarti apa pun yang ada konsensus tentang dalam komunitas algoritma, apa yang diajarkan dalam kursus algoritma, dll. Maksud saya adalah, bahwa tampaknya tidak ada konsensus tentang apa arti notasi itu.

Kristoffer Arnsfelt Hansen