Notasi Asymptotic dan Analisis Apriori
Dalam perancangan Algoritma, analisis kompleksitas suatu algoritma merupakan aspek yang esensial. Terutama, kompleksitas algoritmik berkaitan dengan kinerjanya, seberapa cepat atau lambat kerjanya.
Kompleksitas suatu algoritma menggambarkan efisiensi algoritma dalam hal jumlah memori yang dibutuhkan untuk memproses data dan waktu pemrosesan.
Kompleksitas algoritma dianalisis dalam dua perspektif: Time dan Space.
Kompleksitas Waktu
Ini adalah fungsi yang menjelaskan jumlah waktu yang diperlukan untuk menjalankan algoritme dalam hal ukuran input. "Waktu" dapat berarti jumlah akses memori yang dilakukan, jumlah perbandingan antara bilangan bulat, berapa kali beberapa loop dalam dijalankan, atau beberapa unit alami lainnya yang terkait dengan jumlah waktu nyata yang dibutuhkan algoritme.
Kompleksitas Ruang
Ini adalah fungsi yang menjelaskan jumlah memori yang diambil algoritme dalam hal ukuran input ke algoritme. Kita sering berbicara tentang memori "ekstra" yang dibutuhkan, tidak termasuk memori yang dibutuhkan untuk menyimpan input itu sendiri. Sekali lagi, kami menggunakan satuan alami (tapi panjang tetap) untuk mengukurnya.
Kompleksitas ruang terkadang diabaikan karena ruang yang digunakan minimal dan / atau jelas, namun terkadang hal itu menjadi masalah yang sama pentingnya dengan waktu.
Notasi Asymptotic
Waktu eksekusi suatu algoritme bergantung pada set instruksi, kecepatan prosesor, kecepatan I / O disk, dll. Karenanya, kami memperkirakan efisiensi algoritme secara asimtotik.
Fungsi waktu dari suatu algoritma diwakili oleh T(n), dimana n adalah ukuran masukan.
Berbagai jenis notasi asimtotik digunakan untuk merepresentasikan kompleksitas algoritme. Notasi asimtotik berikut digunakan untuk menghitung kompleksitas waktu berjalan dari suatu algoritma.
O - Big Oh
Ω - Omega besar
θ - Theta besar
o - Little Oh
ω - Sedikit omega
O: Batas Atas Asymptotic
'O' (Big Oh) adalah notasi yang paling umum digunakan. Sebuah fungsif(n) dapat diwakili adalah urutan g(n) itu adalah O(g(n)), jika ada nilai bilangan bulat positif n sebagai n0 dan konstanta positif c sedemikian rupa sehingga -
$ f (n) \ leqslant cg (n) $ untuk $ n> n_ {0} $ dalam semua kasus
Karenanya, fungsi g(n) adalah batas atas untuk fungsi f(n), sebagai g(n) tumbuh lebih cepat dari f(n).
Contoh
Mari kita pertimbangkan fungsi yang diberikan, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Mempertimbangkan $ g (n) = n ^ 3 $,
$ f (n) \ leqslant 5.g (n) $ untuk semua nilai $ n> 2 $
Oleh karena itu, kompleksitas f(n) dapat direpresentasikan sebagai $ O (g (n)) $, yaitu $ O (n ^ 3) $
Ω: Batas Bawah Asymptotic
Kita mengatakan bahwa $ f (n) = \ Omega (g (n)) $ ketika ada konstanta c bahwa $ f (n) \ geqslant cg (n) $ untuk semua nilai yang cukup besar n. Sininadalah bilangan bulat positif. Artinya fungsig adalah batas bawah untuk fungsi f; setelah nilai tertentun, f tidak akan pernah pergi ke bawah g.
Contoh
Mari kita pertimbangkan fungsi yang diberikan, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.
Mempertimbangkan $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ untuk semua nilai $ n> 0 $.
Oleh karena itu, kompleksitas f(n) dapat direpresentasikan sebagai $ \ Omega (g (n)) $, yaitu $ \ Omega (n ^ 3) $
θ: Asymptotic Tight Bound
Kita mengatakan bahwa $ f (n) = \ theta (g (n)) $ ketika ada konstanta c1 dan c2 bahwa $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ untuk semua nilai yang cukup besar dari n. Sinin adalah bilangan bulat positif.
Artinya fungsi g adalah batasan yang ketat untuk fungsi f.
Contoh
Mari kita pertimbangkan fungsi yang diberikan, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Mempertimbangkan $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ untuk semua nilai besar dari n.
Oleh karena itu, kompleksitas f(n) dapat direpresentasikan sebagai $ \ theta (g (n)) $, yaitu $ \ theta (n ^ 3) $.
O - Notasi
Batas atas asimtotik yang disediakan oleh O-notationmungkin ketat atau mungkin tidak asimtotik. Batas $ 2.n ^ 2 = O (n ^ 2) $ ketat secara asimtotik, tetapi batas $ 2.n = O (n ^ 2) $ tidak.
Kita gunakan o-notation untuk menunjukkan batas atas yang tidak kencang secara asimtotik.
Kami mendefinisikan secara resmi o(g(n)) (sedikit-oh dari g n) sebagai himpunan f(n) = o(g(n)) untuk konstanta positif $ c> 0 $ dan terdapat nilai $ n_ {0}> 0 $, sehingga $ 0 \ leqslant f (n) \ leqslant cg (n) $.
Secara intuitif, di o-notation, fungsinya f(n) menjadi relatif tidak signifikan terhadap g(n) sebagai nmendekati tak terbatas; itu adalah,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$
Contoh
Mari kita pertimbangkan fungsi yang sama, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Mempertimbangkan $ g (n) = n ^ {4} $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ kanan) = 0 $$
Oleh karena itu, kompleksitas f(n) dapat direpresentasikan sebagai $ o (g (n)) $, yaitu $ o (n ^ 4) $.
ω - Notasi
Kita gunakan ω-notationuntuk menunjukkan batas bawah yang tidak kencang secara asimtotik. Namun secara formal, kami mendefinisikanω(g(n)) (sedikit-omega dari g dari n) sebagai set f(n) = ω(g(n)) untuk setiap konstanta positif C > 0 dan terdapat nilai $ n_ {0}> 0 $, sehingga $ 0 \ leqslant cg (n) <f (n) $.
Misalnya, $ \ frac {n ^ 2} {2} = \ omega (n) $, tetapi $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. Relasi $ f (n) = \ omega (g (n)) $ menyiratkan bahwa batas berikut ada
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$
Itu adalah, f(n) menjadi relatif besar secara sewenang-wenang g(n) sebagai n mendekati tak terbatas.
Contoh
Mari kita pertimbangkan fungsi yang sama, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Mempertimbangkan $ g (n) = n ^ 2 $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ kanan) = \ infty $$
Oleh karena itu, kompleksitas f(n) dapat direpresentasikan sebagai $ o (g (n)) $, yaitu $ \ omega (n ^ 2) $.
Analisis Apriori dan Apostiari
Analisis apriori artinya, analisis dilakukan sebelum dijalankan pada sistem tertentu. Analisis ini merupakan tahapan dimana suatu fungsi didefinisikan menggunakan beberapa model teoritis. Oleh karena itu, kami menentukan kompleksitas ruang dan waktu dari suatu algoritme dengan hanya melihat algoritme tersebut daripada menjalankannya pada sistem tertentu dengan memori, prosesor, dan kompiler yang berbeda.
Analisis apostiari suatu algoritma berarti kita melakukan analisis suatu algoritma hanya setelah menjalankannya pada suatu sistem. Ini secara langsung tergantung pada sistem dan perubahan dari sistem ke sistem.
Dalam suatu industri, kami tidak dapat melakukan analisis Apostiari karena perangkat lunak umumnya dibuat untuk pengguna anonim, yang menjalankannya pada sistem yang berbeda dari yang ada di industri.
Di Apriori, itulah alasan mengapa kami menggunakan notasi asimtotik untuk menentukan kompleksitas ruang dan waktu saat mereka berubah dari komputer ke komputer; namun, secara asimtotik keduanya sama.