Theta Besar dan Notasi Asymptotic Dijelaskan

Big Omega memberi tahu kita batas bawah waktu proses suatu fungsi, dan Big O memberi tahu kita batas atasnya.

Sering kali, keduanya berbeda dan kami tidak dapat memberikan jaminan pada waktu proses - ini akan bervariasi antara dua batasan dan input. Tapi apa yang terjadi jika keduanya sama? Kemudian kita dapat memberikan batasan theta (Θ) - fungsi kita akan berjalan pada saat itu, tidak peduli masukan apa yang kita berikan.

Secara umum, kami selalu ingin memberikan penjilidan theta jika memungkinkan karena itu adalah penjilidan yang paling akurat dan ketat. Jika kita tidak bisa memberikan ikatan theta, hal terbaik berikutnya adalah ikatan O seketat mungkin.

Ambil, misalnya, 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
  1. Kasus apa yang terbaik? Nah, jika array yang kita berikan nilainya 0 sebagai nilai pertama, maka akan memakan waktu yang konstan: Ω (1)
  2. Apa kasus terburuknya? Jika array tidak berisi 0, kita akan melakukan iterasi ke seluruh array: O (n)

Kami telah memberinya omega dan O terikat, jadi bagaimana dengan theta? Kami tidak bisa memberikannya! Bergantung pada array yang kita berikan, runtime akan berada di antara konstan dan linier.

Mari kita ubah sedikit kode kita.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

Bisakah Anda memikirkan kasus terbaik dan kasus terburuk ?? Saya tidak bisa! Tidak peduli array apa yang kita berikan, kita harus mengulang setiap nilai dalam array. Jadi fungsi ini akan memakan waktu SETIDAKNYA n waktu (Ω (n)), tetapi kita juga tahu itu tidak akan memakan waktu lebih lama dari n waktu (O (n)). Apa artinya ini? Fungsi kita akan mengambil persis n waktu: Θ (n).

Jika batasannya membingungkan, pikirkan seperti ini. Kami memiliki 2 angka, x dan y. Diketahui bahwa x <= y dan y <= x. Jika x kurang dari atau sama dengan y, dan y kurang dari atau sama dengan x, maka x harus sama dengan y!

Jika Anda terbiasa dengan daftar tertaut, uji diri Anda dan pikirkan tentang runtime untuk masing-masing fungsi ini!

  1. Dapatkan
  2. menghapus
  3. Menambahkan

Hal-hal menjadi lebih menarik ketika Anda mempertimbangkan daftar tertaut ganda!

Notasi Asymptotic

Bagaimana kita mengukur nilai kinerja algoritma?

Pertimbangkan bagaimana waktu adalah salah satu sumber daya kita yang paling berharga. Dalam komputasi, kita dapat mengukur kinerja dengan jumlah waktu yang dibutuhkan untuk menyelesaikan suatu proses. Jika data yang diproses oleh dua algoritma sama, kita dapat memutuskan implementasi terbaik untuk menyelesaikan suatu masalah.

Kami melakukan ini dengan menentukan batas matematika dari suatu algoritma. Ini adalah big-O, big-omega, dan big-theta, atau notasi asimtotik dari suatu algoritme. Pada grafik, big-O akan menjadi algoritme terpanjang yang dapat digunakan untuk kumpulan data tertentu, atau "batas atas". Big-omega adalah kebalikan dari big-O, “batas bawah”. Di situlah algoritme mencapai kecepatan tertinggi untuk kumpulan data apa pun. Theta besar adalah nilai performa yang tepat dari algoritme, atau rentang yang berguna antara batas atas dan bawah yang sempit.

Beberapa contoh:

  • “Pengiriman akan ada dalam hidup Anda.” (besar-O, batas atas)
  • "Aku bisa membayarmu setidaknya satu dolar." (omega besar, batas bawah)
  • “Suhu paling tinggi hari ini akan menjadi 25ºC dan paling rendah akan menjadi 19ºC.” (big-theta, sempit)
  • “Jaraknya satu kilometer ke pantai.” (big-theta, tepat)

Informasi Lebih 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-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/