Apa perbedaan antara batas bawah dan batas ketat?

Dengan referensi jawaban ini , apa itu Theta (terikat erat)?

Omega adalah batas bawah, cukup dimengerti, waktu minimum yang dibutuhkan suatu algoritma. Dan kita tahu Big-O untuk batas atas, artinya waktu maksimum yang dibutuhkan algoritme. Tapi saya tidak tahu tentang Theta.

O besar adalah batas atas, sedangkan Omega adalah batas bawah. Theta membutuhkan Big O dan Omega, jadi itulah mengapa ini disebut sebagai ikatan ketat (harus batas atas dan bawah).

Misalnya, pengambilan algoritme Omega(n log n)membutuhkan n log nwaktu setidaknya , tetapi tidak memiliki batas atas. Pengambilan algoritme Theta(n log n)jauh lebih disukai karena membutuhkan setidaknya n log n (Omega n log n) dan tidak lebih dari n log n (O n log n Besar).

Notasi Θ ( notasi theta) disebut rapat karena lebih presisi daripada notasi O dan notasi Ω (notasi omega).

Jika saya malas, saya dapat mengatakan bahwa pencarian biner pada array yang diurutkan adalah O (n ² ), O (n ³ ), dan O (2 ⁿ ), dan secara teknis saya akan benar dalam setiap kasus. Itu karena notasi-O hanya menentukan batas atas , dan pencarian biner dibatasi di sisi atas oleh semua fungsi itu, hanya saja tidak terlalu dekat. Perkiraan malas ini tidak akan berguna .

Notasi-sol menyelesaikan masalah ini dengan menggabungkan notasi-O dan notasi-Ω. Jika saya mengatakan bahwa pencarian biner adalah Θ (log n), itu memberi Anda informasi yang lebih tepat. Ini memberi tahu Anda bahwa algoritme dibatasi di kedua sisi oleh fungsi yang diberikan, jadi tidak akan pernah lebih cepat atau lebih lambat dari yang dinyatakan.

Jika ada sesuatu yang O (f (n)) berarti ada k , g (n) sehingga f (n) ≤ kg (n) .

Jika ada sesuatu yang Ω (f (n)) artinya ada k , g (n) sehingga f (n) ≥ kg (n) .

Dan jika Anda memiliki sesuatu dengan O (f (n)) dan Ω (f (n)) , maka itu adalah Θ (f (n) .

The Artikel Wikipedia layak, jika padat sedikit.

Batas atas asimtotik berarti bahwa algoritme tertentu dijalankan selama jumlah waktu maksimum, bergantung pada jumlah input.

Mari kita ambil algoritma pengurutan sebagai contoh. Jika semua elemen dari sebuah array dalam urutan menurun, maka untuk mengurutkannya, akan memakan waktu berjalan O(n), menunjukkan kompleksitas batas atas. Jika array sudah diurutkan, nilainya akan menjadi O(1).

Umumnya O-notationdigunakan untuk kompleksitas batas atas.

Batas ketat asimtotik (c ₁ g (n) ≤ f (n) ≤ c ₂ g (n)) menunjukkan kompleksitas batas rata-rata untuk suatu fungsi, memiliki nilai antara batas batas (batas atas dan batas bawah), di mana c ₁ dan c ₂ adalah konstanta.

Ungkapan waktu minimum dan waktu maksimum agak menyesatkan di sini. Ketika kita berbicara tentang notasi O besar, ini bukan waktu yang sebenarnya kita minati, ini adalah bagaimana waktu bertambah ketika ukuran input kita semakin besar. Dan biasanya waktu kasus rata-rata atau terburuk yang kita bicarakan, bukan kasus terbaik , yang biasanya tidak bermakna dalam menyelesaikan masalah kita.

Menggunakan pencarian larik dalam jawaban yang diterima untuk pertanyaan lain sebagai contoh. Waktu yang diperlukan untuk menemukan angka tertentu dalam daftar ukuran n rata-rata n / 2 * some_constant. Jika Anda memperlakukannya sebagai suatu fungsi f(n) = n/2*some_constant, itu meningkat tidak lebih cepat dari g(n) = n, dalam arti seperti yang diberikan oleh Charlie. Juga, itu meningkat tidak lebih lambat dari g(n)keduanya. Oleh karena itu, g(n)sebenarnya merupakan batas atas dan batas bawah f(n)dalam notasi Big-O, jadi kompleksitas pencarian linier adalah tepat n , yang berarti Theta (n).

Dalam hal ini, penjelasan dalam jawaban yang diterima untuk pertanyaan lain tidak sepenuhnya benar, yang mengklaim bahwa O (n) adalah batas atas karena algoritme dapat berjalan dalam waktu konstan untuk beberapa input (ini adalah kasus terbaik yang saya sebutkan di atas, yang sebenarnya bukan yang ingin kami ketahui tentang waktu berjalan).

Jika saya malas, saya dapat mengatakan bahwa pencarian biner pada array yang diurutkan adalah O (n2), O (n3), dan O (2n), dan secara teknis saya akan benar dalam setiap kasus.

Kita bisa menggunakan o-notation ("little-oh") untuk menunjukkan batas atas yang tidak rapat secara asimtotik. Baik besar-oh maupun kecil-oh serupa. Tapi, besar-oh kemungkinan besar digunakan untuk mendefinisikan batas atas yang ketat secara asimtotik.

Tepatnya batas bawah atau $ \ omega $ bfon f (n) berarti himpunan fungsi yang secara asimtotik kurang atau sama dengan f (n) yaitu U g (n) ≤ cf (n) $ \ untuk semua $ `un≥ n 'Untuk beberapa c, n' $ \ dalam $ $ \ Bbb {N} $

Dan batas atas atau $ \ mathit {O} $ on f (n) berarti himpunan fungsi yang secara asimtotik lebih besar atau sama dengan f (n) yang secara matematis mengatakan,

$ g (n) \ ge cf (n) \ untuk semua n \ ge n '$, untuk beberapa c, n' $ \ in $ $ \ Bbb {N} $.

Sekarang $ \ Theta $ adalah perpotongan dari dua tulisan di atas

$\theta $

Seperti jika algoritme seperti "persis $ \ Omega \ kiri (f (n) \ kanan $" maka lebih baik mengatakan $ \ Theta \ kiri (f (n) \ kanan) $.

Atau, kita dapat mengatakan juga bahwa itu memberi kita kecepatan sebenarnya yang $ \omega $memberi kita batas terendah.

Perbedaan mendasar antara

Blockquote

Asymptotically upper bound dan asimtotically tight Asym.upperbound berarti algorythm tertentu yang dapat dieksekusi dengan jumlah waktu maksimum tergantung pada jumlah input, misalnya dalam pengurutan algo jika semua elemen array (n) berada dalam urutan menurun maka untuk menaikinya akan mengambil waktu berjalan O (n) yang menunjukkan kompleksitas batas atas, tetapi jika sudah diurutkan maka akan mengambil ohm (1). jadi kami umumnya menggunakan notasi "O" untuk kompleksitas batas atas.

Asym. batas terikat menunjukkan untuk misalnya (c1g (n) <= f (n) <= c2g (n)) menunjukkan batas terikat sedemikian rupa sehingga fungsi memiliki nilai di antara dua batas (batas atas dan batas bawah), memberikan kasus rata-rata.