Perbedaan antara Notasi Big-O dan Little-O

Jawaban:

442

f ∈ O (g) mengatakan, pada dasarnya

Untuk setidaknya satu pilihan konstan k > 0, Anda dapat menemukan sebuah konstanta suatu sehingga ketidaksamaan 0 <= f (x) <= kg (x) berlaku untuk semua x> a.

Perhatikan bahwa O (g) adalah himpunan semua fungsi tempat kondisi ini berlaku.

f ∈ o (g) mengatakan, pada dasarnya

Untuk setiap pilihan konstan k > 0, Anda dapat menemukan sebuah konstanta suatu sehingga ketidaksamaan 0 <= f (x) <kg (x) berlaku untuk semua x> a.

Sekali lagi, perhatikan bahwa o (g) adalah himpunan.

Dalam Big-O, Anda hanya perlu menemukan pengganda tertentu k yang ketidaksamaannya melebihi beberapa minimum x .

Dalam Little-o, harus ada minimum x setelah ketimpangan itu berlaku tidak peduli seberapa kecil Anda menghasilkan k , selama itu tidak negatif atau nol.

Keduanya menggambarkan batas atas, meskipun agak kontra-intuitif, Little-o adalah pernyataan yang lebih kuat. Ada jarak yang jauh lebih besar antara tingkat pertumbuhan f dan g jika f ∈ o (g) daripada jika f ∈ O (g).

Satu ilustrasi perbedaan adalah ini: f ∈ O (f) benar, tetapi f ∈ o (f) salah. Oleh karena itu, Big-O dapat dibaca sebagai "f ∈ O (g) berarti bahwa pertumbuhan asimptotik f tidak lebih cepat dari g", sedangkan "f ∈ o (g) berarti bahwa pertumbuhan asimtotik f benar-benar lebih lambat daripada g". Ini seperti <=versus <.

Lebih khusus lagi, jika nilai g (x) adalah kelipatan konstan dari nilai f (x), maka f ∈ O (g) benar. Inilah sebabnya Anda bisa menghilangkan konstanta saat bekerja dengan notasi O-besar.

Namun, agar f ∈ o (g) benar, maka g harus memasukkan kekuatan x yang lebih tinggi dalam formulanya, sehingga pemisahan relatif antara f (x) dan g (x) harus benar-benar menjadi lebih besar karena x semakin besar.

Untuk menggunakan contoh matematika murni (alih-alih merujuk pada algoritma):

Berikut ini benar untuk Big-O, tetapi tidak akan benar jika Anda menggunakan sedikit-o:

  • x² ∈ O (x²)
  • x² ∈ O (x² + x)
  • x² ∈ O (200 * x²)

Berikut ini berlaku untuk little-o:

  • x² ∈ o (x³)
  • x² ∈ o (x!)
  • ln (x) ∈ o (x)

Perhatikan bahwa jika f ∈ o (g), ini berarti f ∈ O (g). misalnya x² ∈ o (x³) sehingga benar juga bahwa x² ∈ O (x³), (sekali lagi, anggap O sebagai <=dan o sebagai <)

Tyler McHenry
sumber
146
Ya - perbedaannya terletak pada apakah kedua fungsi tersebut secara asimtotik sama. Secara intuitif saya suka memikirkan makna O-besar "tumbuh tidak lebih cepat dari" (yaitu tumbuh pada tingkat yang sama atau lebih lambat) dan sedikit-o makna "tumbuh lebih lambat dari".
Phil
12
Salin ini ke wikipedia? Ini jauh lebih baik daripada apa yang ada di sana.
cloudsurfin
1
@ SA Ya. Itu adalah kasus yang lebih sulit di mana aturan sederhana yang saya berikan tentang "kekuatan x yang lebih tinggi" jelas tidak berlaku. Tetapi jika Anda melihat definisi batasan yang lebih ketat yang diberikan dalam jawaban Strilanc di bawah ini, yang ingin Anda ketahui adalah apakah lim n-> inf (2 ^ n / 3 ^ n) = 0 Sejak (2 ^ n / 3 ^ n) = (2/3) ^ n dan karena untuk setiap 0 <= x <1, lim n-> inf (x ^ n) = 0, memang benar bahwa 2 ^ n = o (3 ^ n).
Tyler McHenry
1
Berhati-hatilah dengan "Di Little-o, harus ada minimum x setelah ketimpangan itu berlaku tidak peduli seberapa kecil Anda menghasilkan k, asalkan tidak negatif atau nol." Ini bukan "untuk setiap aada kyang: ...", itu "untuk setiap kada ayang: ..."
GA1
1
"Di Little-o, harus ada minimum x setelah ketimpangan itu berlaku tidak peduli seberapa kecil Anda menghasilkan k, asalkan tidak negatif atau nol." tidak, ini tidak benar.
Filippo Costa
196

Big-O adalah untuk sedikit-o sebagaimana ≤adanya <. Big-O adalah batas atas inklusif, sedangkan little-o adalah batas atas yang ketat.

Misalnya, fungsinya f(n) = 3nadalah:

  • di O(n²), o(n²), danO(n)
  • tidak O(lg n), o(lg n)atauo(n)

Secara analog, angkanya 1adalah:

  • ≤ 2,, < 2dan≤ 1
  • tidak ≤ 0, < 0atau< 1

Ini sebuah tabel, menunjukkan ide umum:

Meja besar

(Catatan: tabel adalah panduan yang baik tetapi definisi batasnya harus dalam hal batas superior daripada batas normal. Misalnya, 3 + (n mod 2) berosilasi antara 3 dan 4 selamanya. O(1)Meskipun tidak memiliki batas normal, karena masih memiliki batas a lim sup: 4.)

Saya sarankan untuk mengingat bagaimana notasi Big-O dikonversi menjadi perbandingan asimptotik. Perbandingannya lebih mudah diingat, tetapi kurang fleksibel karena Anda tidak bisa mengatakan hal-hal seperti n O (1) = P.

Craig Gidney
sumber
Saya punya satu pertanyaan: apa perbedaan antara baris 3 dan 4 (batas definisi kolom)? Bisakah Anda tunjukkan satu contoh di mana 4 memegang (lim> 0), tetapi tidak 3?
Masked Man
3
Oh, aku sudah menemukan jawabannya. Big Omega adalah untuk lim> 0, Big Oh adalah untuk lim <infinity, Big Theta adalah ketika kedua kondisi bertahan, artinya 0 <lim <infinity.
Masked Man
Untuk f ∈ Ω (g), bukankah seharusnya batas infinity menjadi> = 1? Demikian pula untuk f ∈ O (g), 1 = <c <∞?
user2963623
1
@ user2963623 Tidak, karena nilai hingga benar-benar di atas 0, termasuk nilai antara 0 dan 1, sesuai dengan "kompleksitas asimtotik yang sama tetapi faktor konstan yang berbeda". Jika Anda menghilangkan nilai di bawah 1, Anda memiliki cutoff di ruang faktor konstan bukan di ruang kompleksitas asimptotik.
Craig Gidney
1
@ubadub Anda menyiarkan operasi eksponensial selama set. Ini notasi longgar.
Craig Gidney
45

Saya menemukan bahwa ketika saya tidak dapat memahami sesuatu secara konseptual, memikirkan mengapa seseorang akan menggunakan X sangat membantu untuk memahami X. (Belum lagi Anda belum mencobanya, saya hanya mengatur panggung.)

[hal-hal yang Anda ketahui] Cara umum untuk mengklasifikasikan algoritma adalah dengan runtime, dan dengan mengutip kompleksitas algoritma-Oh yang besar, Anda bisa mendapatkan estimasi yang cukup bagus tentang mana yang "lebih baik" - mana saja yang memiliki fungsi "terkecil" di dalam O! Bahkan di dunia nyata, O (N) "lebih baik" dari O (N²), kecuali hal-hal konyol seperti konstanta super-masif dan sejenisnya.

Katakanlah ada beberapa algoritma yang berjalan di O (N). Cukup bagus, ya? Tapi katakanlah Anda (Anda orang yang cerdas, Anda) datang dengan algoritma yang berjalan di O ( N ⁄ loglogloglogN ). YAY! Lebih cepat! Tetapi Anda akan merasa konyol menulis itu berulang-ulang ketika Anda menulis tesis Anda. Jadi Anda menulisnya sekali, dan Anda dapat mengatakan "Dalam makalah ini, saya telah membuktikan bahwa algoritma X, yang sebelumnya dapat dihitung dalam waktu O (N), sebenarnya dapat dihitung dalam o (n)."

Dengan demikian, semua orang tahu bahwa algoritme Anda lebih cepat --- seberapa banyak yang tidak jelas, tetapi mereka tahu lebih cepat. Secara teoretis. :)

agorenst
sumber