Big Omega memberitahu kita batas bawah runtime suatu fungsi, dan Big O memberitahu kita batas atas.
Sering kali, ia berbeza dan kami tidak dapat memberikan jaminan pada waktu berjalan - ia akan berbeza antara dua batas dan input. Tetapi apa yang berlaku apabila mereka sama? Kemudian kita dapat memberikan theta (Θ) - fungsi kita akan berjalan pada masa itu, tidak kira apa input yang kita berikan.
Secara amnya, kami selalu mahu memberikan theta terikat jika boleh kerana itu adalah ikatan yang paling tepat dan ketat. Sekiranya kita tidak dapat memberikan ikatan theta, perkara terbaik seterusnya adalah ikatan O yang paling ketat.
Ambil, sebagai contoh, fungsi yang mencari array untuk nilai 0:
def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false- Apa kes terbaik? Jika array yang kita berikan mempunyai 0 sebagai nilai pertama, ia memerlukan masa yang berterusan: Ω (1)
- Apakah kes terburuk? Sekiranya array tidak mengandungi 0, kita akan berulang melalui keseluruhan array: O (n)
Kami telah memberikannya omega dan O, jadi bagaimana dengan theta? Kami tidak dapat memberikannya! Bergantung pada susunan yang kami berikan, waktu proses akan berada di antara pemalar dan linier.
Mari ubah kod kami sedikit.
def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)Bolehkah anda memikirkan kes terbaik dan terburuk ?? Saya tidak boleh! Tidak kira apa jua array yang kita berikan, kita mesti mengulang setiap nilai dalam array. Oleh itu, fungsinya akan memakan masa LEPASAN (Ω (n)), tetapi kita juga tahu bahawa ia tidak akan memakan masa lebih lama daripada waktu n (O (n)) Apakah maksud ini? Fungsi kami akan mengambil masa tepat : Θ (n).
Sekiranya batasannya mengelirukan, fikirkanlah seperti ini. Kami mempunyai 2 nombor, x dan y. Kami diberi bahawa x <= y dan y <= x. Sekiranya x kurang daripada atau sama dengan y, dan y kurang daripada atau sama dengan x, maka x harus sama dengan y!
Sekiranya anda sudah biasa dengan senarai terpaut, uji sendiri dan fikirkan masa jalan untuk setiap fungsi ini!
- dapatkan
- buang
- Tambah
Perkara menjadi lebih menarik apabila anda mempertimbangkan senarai yang mempunyai kaitan dua kali ganda!
Notasi Asimptotik
Bagaimana kita mengukur nilai prestasi algoritma?
Pertimbangkan bagaimana masa adalah salah satu sumber paling berharga kita. Dalam pengkomputeran, kita dapat mengukur prestasi dengan jumlah masa yang diperlukan proses untuk diselesaikan. Sekiranya data yang diproses oleh dua algoritma adalah sama, kita dapat memutuskan pelaksanaan terbaik untuk menyelesaikan masalah.
Kami melakukan ini dengan menentukan had matematik algoritma. Ini adalah big-O, big-omega, dan big-theta, atau notasi asimptotik algoritma. Pada grafik, O-besar akan menjadi yang paling lama yang dapat diambil algoritma untuk set data tertentu, atau "batas atas". Big-omega adalah seperti kebalikan dari big-O, "batas bawah". Di situlah algoritma mencapai kelajuan tertinggi untuk sebarang set data. Big theta adalah nilai prestasi tepat algoritma, atau julat berguna antara sempadan atas dan bawah yang sempit.
Beberapa contoh:
- "Penghantaran akan sampai di sana sepanjang hayat anda." (besar-O, batas atas)
- "Saya boleh membayar anda sekurang-kurangnya satu dolar." (omega besar, batas bawah)
- "Tinggi hari ini akan menjadi 25ºC dan yang rendah adalah 19 willC." (besar-theta, sempit)
- "Ini satu kilometer berjalan kaki ke pantai." (besar-theta, tepat)
Maklumat lanjut:
//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notasi-mewakili //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/