Definisi tingkat pertumbuhan asimptotik apa yang harus kita ajarkan?

Ketika kita mengikuti buku teks standar, atau tradisi, kebanyakan dari kita mengajarkan definisi notasi besar-Oh berikut dalam beberapa kuliah pertama kelas algoritme: Mungkin kita bahkan memberikan seluruh daftar dengan semua bilangannya:

1. $f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
2. $f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
3. $f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
4. $f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$
5. $f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$ .

Namun, karena definisi ini tidak begitu mudah untuk dikerjakan ketika harus membuktikan bahkan hal-hal sederhana seperti , kebanyakan dari kita dengan cepat bergerak untuk memperkenalkan "trik batas":$5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$

1. $f = o(g)$ jika ada dan 0 ,$\lim_{n \rightarrow \infty} f(n)/g(n)$$0$
2. $f = O(g)$ jika $\lim_{n \rightarrow \infty} f(n)/g(n)$ ada dan bukan $+\infty$ ,
3. $f = \Theta(g)$ jika $\lim_{n \rightarrow \infty} f(n)/g(n)$ ada dan bukan $0$ atau $+\infty$ ,
4. $f = \Omega(g)$ jika $\lim_{n \rightarrow \infty} f(n)/g(n)$ ada dan tidak $0$ ,
5. $f = \omega(g)$ jika $\lim_{n \rightarrow \infty} f(n)/g(n)$ ada dan $+\infty$ .

Pertanyaanku adalah:

Apakah itu menjadi kerugian besar untuk mengajar kelas algoritma sarjana untuk mengambil kondisi batas sebagai yang definisi $o$ , $O$ , $\Theta$ , $\Omega$ , dan $\omega$ ? Itulah yang akhirnya kita semua gunakan dan tampaknya cukup jelas bagi saya bahwa melompati definisi kuantifikasi membuat hidup semua orang lebih mudah.

Saya akan tertarik untuk mengetahui apakah Anda telah menemukan beberapa kasus alami yang meyakinkan di mana standar -definisi sebenarnya diperlukan, dan jika tidak, apakah Anda memiliki argumen yang meyakinkan untuk menjaga standar -definisi tetap di muka. c , n $c,n_0$$c,n_0$

Saya lebih suka mengajar definisi asli dengan bilangan.

IMO, manusia umumnya mengalami kesulitan dalam memahami rumus dan definisi dengan lebih dari dua pergantian pembilang secara langsung. Memperkenalkan bilangan baru dapat memperjelas apa arti definisi tersebut. Di sini, dua bilangan terakhir hanya berarti "untuk semua n cukup besar", memperkenalkan jenis kuantifikasi ini dapat membantu.

Gambar yang saya gambar untuk menjelaskan konsep-konsep ini lebih cocok dengan versi quantifier.

Saya pikir penyederhanaan batas berguna untuk mahasiswa teknik yang hanya tertarik menghitung tingkat pertumbuhan, tetapi tidak akan berguna bagi siswa ilmu komputer. Bahkan, menggunakan penyederhanaan ini dapat menyebabkan lebih banyak kerugian daripada kebaikan.

Ide ini mirip dengan saran bahwa kita menggunakan aturan untuk menghitung turunan (polinomial, eksponensial, ..., aturan rantai, ...) sebagai ganti definisi epsilon-delta tentang itu, yang IMHO bukan ide yang baik.

Sunting: Revisi utama dalam revisi 3.

Karena saya belum pernah mengajar kelas, saya tidak berpikir bahwa saya dapat mengklaim sesuatu dengan meyakinkan tentang apa yang harus kita ajarkan. Namun demikian, inilah yang saya pikirkan.

Ada contoh alami di mana "trik batas" seperti yang ditulis tidak dapat diterapkan. Sebagai contoh, misalkan Anda menerapkan "vektor panjang variabel" (seperti vektor <T> dalam C ++) dengan menggunakan array panjang tetap dengan pengganda ukuran (yaitu, setiap kali Anda akan melebihi ukuran array, Anda realokasi array dua kali lebih besar dari sekarang dan salin semua elemen). Ukuran S ( n ) dari array ketika kita menyimpan elemen n dalam vektor adalah kekuatan terkecil 2 lebih besar dari atau sama dengan n . Kami ingin mengatakan bahwa S ( n ) = O ( n ), tetapi menggunakan "batas trik" seperti yang tertulis sebagai definisi tidak akan memungkinkan kami untuk melakukannya karena S ( n) / n terombang-ambing dalam kisaran [1,2). Hal yang sama berlaku untuk Ω () dan Θ ().

Sebagai masalah yang agak terpisah, ketika kami menggunakan notasi ini untuk menggambarkan kompleksitas suatu algoritma, saya pikir definisi Anda tentang Ω () kadang-kadang tidak nyaman (walaupun saya kira definisi itu umum) Lebih mudah untuk mendefinisikan bahwa f ( n ) = Ω ( g ( n )) jika dan hanya jika limsup f ( n ) / g ( n )> 0. Ini karena beberapa masalah sepele untuk banyak nilai tak terhingga n ( seperti masalah maching sempurna pada grafik dengan jumlah ganjil n simpul). Hal yang sama berlaku untuk Θ () dan ω ().

Oleh karena itu, saya pribadi menemukan bahwa definisi berikut yang paling mudah digunakan untuk menggambarkan kompleksitas suatu algoritma: untuk fungsi f , g : ℕ → ℝ _{> 0} ,

• f ( n ) = o ( g ( n )) jika dan hanya jika limsup f ( n ) / g ( n ) = 0. (Ini sama dengan lim f ( n ) / g ( n ) = 0.)
• f ( n ) = O ( g ( n )) jika dan hanya jika limsup f ( n ) / g ( n ) <∞.
• f ( n ) = Θ ( g ( n )) jika dan hanya jika 0 <limsup f ( n ) / g ( n ) <∞.
• f ( n ) = Ω ( g ( n )) jika dan hanya jika limsup f ( n ) / g ( n )> 0. (Ini sama dengan f ( n ) bukan o ( g ( n )).)
• f ( n ) = ω ( g ( n )) jika dan hanya jika limsup f ( n ) / g ( n ) = ∞. (Ini setara dengan yang f ( n ) bukan O ( g ( n )).)

atau yang setara,

• f ( n ) = o ( g ( n )) jika dan hanya jika untuk setiap c > 0, untuk n yang cukup besar , f ( n ) ≤ c ⋅ g ( n ).
• f ( n ) = O ( g ( n )) jika dan hanya jika untuk beberapa c > 0, untuk n yang cukup besar , f ( n ) ≤ c ⋅ g ( n ).
• f ( n ) = Θ ( g ( n )) jika dan hanya jika f ( n ) = O ( g ( n )) dan f ( n ) = Ω ( g ( n )).
• f ( n ) = Ω ( g ( n )) jika dan hanya jika untuk beberapa d > 0, untuk banyak n , f ( n ) ≥ d ⋅ g ( n ).
• f ( n ) = ω ( g ( n )) jika dan hanya jika untuk setiap d > 0, untuk banyak n , f ( n ) ≥ d ⋅ g ( n ).

Tapi saya tidak tahu apakah ini praktik yang biasa atau tidak. Saya juga tidak tahu apakah itu cocok untuk mengajar. Masalahnya adalah bahwa kita terkadang ingin mendefinisikan Ω () dengan liminf sebagai gantinya (seperti yang Anda lakukan pada definisi pertama). Sebagai contoh, ketika kita mengatakan "Probabilitas kesalahan dari algoritma acak ini adalah 2 ^{−Ω ( n )} ," kami tidak berarti bahwa probabilitas kesalahan secara eksponensial kecil hanya untuk banyak n !

Menggunakan batas agak membingungkan karena (1) itu gagasan yang lebih rumit (2) tidak menangkap f = O (g) dengan baik (seperti yang dapat kita lihat dalam diskusi di atas). Saya biasanya berbicara tentang fungsi dari angka Natural (sangat positif) ke angka Natural (yang cukup untuk menjalankan kali), melewatkan hal-hal kecil, dan kemudian definisi yang ringkas dan sesuai untuk undergrad tahun pertama:

Dfn: f = O (g) jika untuk beberapa C untuk semua n kita memiliki f (n) <= C * g (n)

Ketika saya mengambil kursus dasar, kami diberi hal sebagai definisi dan hal-hal lain sebagai teorema.$\exists c,n_0 \dots$

Saya pikir yang pertama lebih alami bagi banyak orang yang berpikir diskrit daripada terus menerus, itulah kebanyakan ilmuwan komputer (dalam pengalaman saya). Hal ini juga sesuai dengan cara yang biasanya kita berbicara tentang hal-hal yang lebih baik: "Ada fungsi polinomial derajat 3 yang merupakan batas atas untuk ini hingga faktor konstan."$f$

Sunting : Anda dapat lebih dekat dengan cara berbicara ini jika Anda menggunakan definisi ini: (Perhatikan bahwa d = f ( n 0 ) menghubungkan definisi ini dengan yang biasanya diberikan)$f \in \mathcal{O}(g) :\Leftrightarrow \exists c,d > 0 \forall n \geq 0 : f(n) \leq c\cdot g(n) + d$$d=f(n_0)$

Batas barang sangat berguna untuk menghitung kelas kompleksitas, yaitu dengan pena dan kertas.

Bagaimanapun, saya pikir ini sangat berguna bagi siswa untuk belajar bahwa ada banyak definisi (semoga) yang setara. Mereka harus dapat menyadari hal itu dan memilih perbedaan jika tidak ada definisi yang sepadan.

Setelah mempelajari konsep-konsep ini hanya beberapa tahun yang lalu, mereka bukan yang paling sulit untuk dipahami untuk kelas saya (sebagai lawan dari konsep-konsep seperti induksi, atau kontra positif). Batas dan limsup hanya lebih "intuitif" bagi mereka yang akrab dengan kalkulus menurut saya. Tetapi siswa dengan landasan matematika seperti itu akan memiliki latar belakang teori-set, sehingga mereka dapat memproses kualifikasi diskrit.

Juga, yang lebih penting, ingatlah bahwa pada akhirnya siswa Anda akan melanjutkan (semoga) membaca buku teks teori cs lainnya, dan mungkin bahkan makalah penelitian suatu hari nanti. Dengan demikian, lebih baik bagi mereka untuk merasa nyaman dengan notasi standar di lapangan, bahkan jika itu tidak idealnya disusun pada awalnya. Tidak ada salahnya memberi mereka definisi alternatif juga, setelah mereka mengasimilasi definisi standar.

Untuk penjelasan yang menarik tentang masalah ini, lihat surat yang ditulis dengan baik oleh Don Knuth, "Calculus via O notation" . Dia menganjurkan pandangan sebaliknya bahwa kalkulus harus diajarkan melalui notasi 'A', 'O' dan 'o'.

$x$$A$$y$$x = A(y)$$|x| \leq y$$100$$A(200)$

1. Definisi Tsuyoshi Ito tidak terlihat benar. Untuk little-omega dan big-omega definisi harus menggunakan liminf, bukan limsup. Definisi big-theta membutuhkan batas bawah pada liminf dan batas atas pada limsup.

2. Salah satu definisi dari f (n) = O (g (n)) adalah bahwa terdapat fungsi lain f '(n)> = f (n) sedemikian sehingga lim f' (n) / g (n) <infinity.

3. Mengapa pemula diizinkan untuk mengirim jawaban tetapi tidak memberikan komentar?

Pertama , saya mencoba mengembangkan intuisi pada siswa , sebelum menunjukkan persamaan.

• "Gabungkan-sort vs Sisipan-Sortir" adalah titik awal yang baik.

Aspek lain adalah bahwa hal itu sangat tergantung pada program studi konkret. IMHO tergantung pada mata pelajaran sebelumnya salah satu definisi akan lebih cocok - sementara IMHO masih merupakan ide bagus untuk menunjukkan keduanya dan menerima kedua jenis solusi.