Nah sekarang kita melihat bagaimana computational complexity atau algorithms complexity bekerja untuk menyelesaikan permasalahan yang simple. simple ya nah permasalahan disebut string reconstruction nah bayangkan kalau misalnya untuk o dalam bahasa Indonesianya string reconstruction itu berarti penyusunan kembali string ya nah bayangkan kalau misalnya kita punya input inputnya ini karakter-karakter Sampai saya ganti warnanya karakter-karakter yang tertulis di sini yang sebenarnya kalau kita dengan mata manusia kita bisa dengan cepat memahami kalau input ini, karakter-karakter ini itu membentuk suatu kalimat yang mempunyai makna atau arti dalam hal ini kita bisa melakukan interpretasi kalau seharusnya input ini itu bermakna these are the reasons tapi karena kurangnya atau tidak adanya space atau spasi input ini terlihat seperti tidak ada maknanya padahal itu ada maknanya permasalahannya Kita ingin menyelesaikan masalah ini dengan input ini. Kita berharap outputnya seperti ini supaya dia mempunyai makna.
Dapatkah kita memasukkan? Bagaimana adalah, bagaimana mekanisme? Kita memasukkan space atau spasi ini ke urutan, ke sekelompokan karakter-karakter ini Supaya akhirnya bisa membentuk kalimat these are the reasons ini Dan mekanismenya harus berpikir seperti layaknya komputer berpikir. Nah, kita bisa anggaplah kita diberi dictionary atau istilahnya kamus.
Istilahnya kamus atau kumpulan kata-kata yang bisa kita ambil sebagai contoh untuk membentuk output ini. Kumpulan kata-kata itu adalah adalah misalnya di kamus ada kata dis kemudian ada kata ar-9 ada ada kata juga ada kata reasons kemudian ada kata on Hai kemudian ada kata son Hai nah yang kemudian ada kata reason Hai dan kata-kata yang lainnya sebenarnya ya ini bisanya pakai es ini tidak pakai es ya ya, tapi Tapi itu adalah kata-kata yang umum yang ada di kamus. Lalu bagaimana kita berdasarkan input yang tidak ada stasi ini dan mereferensikan kepada kumpulan kata-kata yang ada di kamus ini.
bisa mengeluarkan output yang seperti ini. Bisa kita memilih cara yang efisien. Misalnya seperti itu.
Kita bisa saja memasukkan spasi di setiap akhir kata ini. Jadi misalnya kita siapkan algoritma, kita tulis algoritma yang mana setiap huruf yang ada di input ini, kita masukkan spasi. Lalu kita cek kita cek ya kalau kita cek Apakah kata tersebut ada dalam kamus kalau ada kita simpan kata tersebut jadi pertama kalau kita masukkan spasi disini ya otomatis berarti T akan terpisah Berarti T akan terpisah dengan Sis karakter sisanya. Kita masukkan spasi di sini. Berarti untuk putaran pertama, T terpisah, spasi, lalu hiser, dan seterusnya.
Lalu kemudian T dicek apakah T ini ada dalam kamus yang disediakan sebagai referensi buat kita. Oh, ternyata tidak ada. Lalu kita buang proses itu, kita lanjutkan ke proses yang berikutnya.
Proses yang berikutnya adalah ketika kita memasukkan spasi setelah T dan H, berarti T, H, spasi, E, S, A, R, E, dan seterusnya. Apakah T dan H ada dalam urutan kamu sini? Tidak ada. Berarti kita lanjutkan ke spasi yang ketiga.
Di penentuan memasukkan spasi yang ketiga di sini. T, H, E, spasi, S, E, A, R, E, dan seterusnya. Dan seterusnya Nah ketika dibandingkan T dan H ini ada disini Yaitu Ada di kampus ini Otomatis T ini akan kita simpan Kita simpan dulu T Nanti kita lanjutkan dengan sini Jadi Untuk penemuan kata pertama Kita telah menemukan kata kita menukar kata The kita simpan dalam istilahnya tempat penyimpanan sementara ya satu kata kita temukan The lalu kita lanjutkan spasi dimasukkan ke yang keempat berarti spasi S sorry Karena katanya ini sudah diambil, maka berikutnya ada S spasi EAR dan seterusnya.
Nah, kalian bisa melihat di sini kalau S ini sudah tidak ada lagi di sini. Kalau kita lanjutkan. Proses yang sama berulang-ulang, S apakah ada?
Tidak ada. SE apakah ada? Tidak ada.
SEA apakah ada? Tidak ada. SEAR apakah ada?
Tidak ada. SERT apakah ada? Tidak ada. Sehingga kemungkinan yang kita temukan hanya huruf D saja. Padahal pemotongan awal, pemotongan yang terlebih dahulu, itu akan membuat susunan kata ini menjadi rusak.
Terlebih lagi, kita ketika memasukkan setiap spasi di sini, itu pasti akan memakan waktu untuk pemrosesan. Ketika kita memilih mekanisme untuk memasukkan setiap spasi di masing-masing karakter, itu adalah hal yang expensive atau adalah hal yang mahal karena memakan proses dan memakan waktu. Belum tentu hasilnya juga betul.
Padahal hasil yang betul adalah this. Tetapi kita sudah melakukan pemotongan awal di kalimat the. Itu kelemahan kalau kita membeli mekanisme untuk memasukkan spasi di setiap kali kita mendapatkan karakter yang sudah mahal belum tentu hasilnya.
betul lalu bagaimana kalau dengan greedy approach sorry, greedy approach dengan greedy approach kita memilih longest valid word artinya memilih kalimat paling panjang yang bisa ditemukan di setiap langkah atau setiap step, tanpa memikirkan konsekuensi di masa yang akan datang atau di langkah selanjutnya untuk kasus ini ya. Jadi kalau kita memilih tadi untuk yang spasi itu pendekatan dengan menggunakan spasi sudah terbukti sangat. tidak efisien ya sangat mahal memakan proses yang lama dan hasilnya juga tidak maksimal salah tidak betul sekarang kita coba dengan greedy approach yaitu kita memilih apa namanya longest valid word ya tapi ini juga tidak selalu betul hasilnya ya bayangkan kalau kita mempunyai apa namanya kita ngambil string yang adalah ambil string yang terakhir nah ini ya the kita punya string the reason ya dan kita masih menggunakan apa namanya Kita masih menggunakan Dictionary yang sama Kamus yang sama Referensi yang sama dengan yang sebelumnya Kita punya kata ini Dari San Kita menggunakan referensi yang ini. Ketika kita memilih melakukannya dengan greedy approach, hampir sama dengan kita memusuhkan spasi, kita akan mendapatkan, kalau the tadi kita bisa exclude secara tiba-tiba.
Tetapi ini bukan kata dengan makna terpanjang, karena yang terpanjang adalah the. jadi kalau ketika kita ambil the awal lalu kita simpan dulu the disini kemudian kita ulangi lagi proses apakah makna yang terpanjang lainnya adalah der kita ambil lagi sini der simpan lagi der der dan der ada karena der ada di sini der oh sebentar der ada der juga ada Tapi kalau kita ambil di sini, kita potong di sini, ambil the ini, itu akan tersisa kata a song. Karena kalau kita lihat the, h, e, r, a, a, ini sudah tidak ada di referensi kita. Jadi yang terpanjang adalah the. Bukan the lagi, adalah the.
Kalau the, sudah kita exclude. kita akan tersisa kata a song akan tersisa kata a song nah a song ini akan terbuang sia-sia karena dia tidak ada dalam referensi kita jadi bahkan dengan greedy approach juga kita tidak bisa menyelesaikan permasalahan yang sistematik ini Jadi padahal kita maunya kalau kita punya kata the reason. Itu kita mau dia jadi the reason.
Bukan the, bukan there a sun. Kalau the reason semua kata pasti akan ada maknanya. Tapi kalau there a sun yang merupakan hasil dari greedy itu tidak ada maknanya. Karena a sun tidak ada maknanya.
Reason ada di ini. There juga ada. Ada there ada this. ada, jadi greedy juga tidak bisa menyelesaikan permasalahan string reconstruction ini Jadi memang diperlukan pemilihan mekanisme yang cukup efisien untuk sebisa mungkin memisahkan karakter-karakter atau merekonstruksi string ini atau karakter-karakter.
karakter yang kita punya ini supaya dia pertama efisien tidak makan computational cost dan juga mempunyai menghasilkan hasil yang masuk akal itu yang nanti kita lihat Oh ya harus kita pikirkan ketika kita membangun ketika kita bicara mengenai algorithmic complexity atau computational complexity Hai ya Nah berikutnya jadi sudah kita lihat bagaimana permasalahan string rekonstruksi ini atau string reconstruction sini itu walaupun terkesan simpel dengan intuisi kita dengan dengan apa namanya apa yang kita lihat kalau kita bisa melihat dengan jelas apalagi yang sudah bisa mungkin familiar dengan bahasa Inggris kalau pemecahan string ini itu sangat mudah itu karena kita memang melihat dengan mata kita dan kita terbiasa dengan dengan mungkin menggunakan bahasa Inggris dalam percakapan. Jadi dengan mudah kita bisa menentukan di mana kita harus meletakkan spasi. Komputer tidak demikian. Komputer harus melakukan perulangan-perulangan yang sistematis untuk secara tepat menetapkan spasi ini, supaya outputnya menjadi lebih bermakna.
Walaupun dengan greedy algorithm yang kemarin sebelumnya, dia menghasilkan output yang salah kalau dilakukan berulang-ulang mungkin pada akhirnya akan mendapatkan hasil yang benar juga Tapi kalau kita berlanya at what cost, dengan harga berapa kita harus membayar kredit algoritm supaya mengeluarkan output yang masuk akal. Nah disinilah kegunaan dari algorithmic complexity. Bagaimana kita bisa menentukan langkah-langkah sistematis yang tepat supaya komputer bisa mengeksekusi langkah-langkah sistematis tersebut. dengan harapan tidak mengakan waktu yang banyak dan tidak makan computational power atau memori yang banyak.
Ini harus diperhentukan apakah kita perlu dynamic programming, lalu perpindahan logik dari apa yang kita lihat di otak kita dan kita bisa cerna dengan mata dan pemikiran kita. Hai ya logikanya kita masukin ke dalam mesin ya kapan mesin harus mengharus menentukan untuk memasukkan spas nah disitu akan berdampak pada time kompleksity Kalau kita bisa menemukan cara yang cerdas, di mana perulangan yang dilakukan oleh komputer itu tidak memakan waktu dan memori, itu artinya algoritma kita menjadi lebih efisien. Hai efisien jadi lain kali ketika kalian melihat ada permasalahan seperti hal-hal yang simpel ini ya jangan serta-merta kalian menganggap Oh itu adalah hal yang mudah dilakukan kemudian Mudah buat manusia, tapi belum tentu buat komputer.
Karena komputer menyelesaikan sesuatu harus dengan instruksi yang jelas dan terstruktur. Nah, mentranslasikan. pengetahuan kita atau logik yang kita punya di otak kita supaya mesin bisa melakukan hal yang sama itu tidak mudah kadang kita mentranslasikan logik kita untuk komputer bisa melakukan hal sama dengan waktu dan space yang expensive atau yang mahal. Itu yang membuat kita harus membuat algoritma kita menjadi lebih efisien.
Nah, kita lihat contoh yang lainnya lagi. Misalnya kalian dikasih input yaitu ini ya, apple pie. Tanpa tanda ini ya. Kalimat awal aksaranya itu apple pie. Outputnya adalah apple space atau spasi pie.
Kalian diberi dictionary atau kamus atau referensi itu apple. Karena ini kata yang ada dalam kamus. Dan pi.
Kita sederhanakan saja ya. Apple dan pi. Kita bisa melakukan perulangan berkali-kali sambil membagi split dari karakter yang ada. Jadi kita bisa bagi misalnya. Sebentar saya ganti.
Siapa dulu ya. Misalnya putaran pertama kita ambil keseluruhan kata, apple pie ini. Artinya kita membagi, kita menghitung fungsi dari karakter kosong sampai karakter ketujuh yaitu apple pie. Nah apakah apple pie ada di kamus?
Tidak ada. Karena tidak ada kita lanjut ke putaran kedua. Putaran kedua kita mulai membagi Antara bagi dua, antara A, yaitu adalah fungsi dari kosong, dari karakter kosong ke karakter kosong, yaitu A, ke karakter 1 sampai karakter 7, artinya Apple ini.
Kalau kita lihat, A apakah ada? Tidak ada. Apple, Apple, tidak ada.
Kalau kita lanjut ke putaran berikutnya, kita bagi. dari F01 yaitu A dan P, kemudian dari karakter ke-2 sampai ke-7, ingat karakter dimulai dari kosong ya, yaitu PL. L, E, P, I. P, I, E kita bandingkan. Ternyata tidak ada.
Lalu berkelanjutan. Terus begitu sampai kita menemukan apa namanya? Sampai kita bisa memisahkan antara Apple dan Pi.
Yang nantinya kalau putaran tersebut terus mekanisme itu terus dilanjutkan dia akan mendapatkan hasil ketika kita membagi karakter F sama dengan oh sorry, fungsi f dari dari karakter kosong yaitu A sampai karakter keempat yaitu ini dan karakter kelima sampai karakter ke-7 yaitu pai karena ketika kita membandingkan Apple dia ada di kamus atau referensi kita, pi kita ada di referensi kita. Jadi ketika dia menghasilkan ini, otomatis dia langsung bisa membagi supaya outputnya menjadi apa yang kita harapkan, apple pi ini. Jadi bagus, hanya kembali lagi pertanyaannya at what cost?
Artinya seberapa mahal cara seperti itu? Tentu saja mahal, karena ada perulangan yang harus dilakukan. Dan ada, dan tidak ada, kalau kita sempat lihat di slide-slide berikutnya, dia tidak memanfaatkan teknik memoization, artinya mengingat apa yang sudah dilakukan sebelumnya, atau kalkulasi sebelumnya. Bayangkan ketika pada saat kita sampai di misalnya ini, sebelum kita sampai ke F0 sama dengan F4, ini kan pasti ada F0,2.
Ada F0,2. Sebelum sampai ke F04, ada F0,2 dan pasangannya. Ada F0,3 dan pasangannya.
Nah, saat kita sampai ke F0,3 ini, Itu kan sebenarnya kita sudah sebelumnya menghitung F0,1, F0,2, F0,0, F0,1, F0,2, F0,3, F0,4 Padahal untuk menghitung sampai ke F0,4 ini sebenarnya kita sudah menghitung F0,0, F0,1 sampai F0,3 kalau misalnya kita menyimpan hasil komputasi dari F0,0 itu berarti kita sudah tidak perlu lagi menghitung F0,0 ulang yang merupakan perhitungan yang ada pada F0,1 ini jadi kalau kita ambil komputasinya Apa yang sudah dihitung di langkah pertama ini yaitu F00 ini Sebenarnya dihitung ulang oleh langkah F01 ini Karena bagaimanapun F01 ini Itu merupakan gabungan antara F00 dan sisanya Dan F11 Begitu pula dengan F0 F02 misalnya. Itu merupakan gabungan antara apa yang sudah dikerjakan dari F00, ditambah F11, ditambah F2,2. Jadi pertunjukan ini kembali diulangi, berulang-ulang sepanjang, sampai pada saat F0,4.
Nah, itulah yang kita sebut dengan repetisi. Hai repetisi ini kalau repetisi ini hanya pada kasus seperti misalnya Hai pola rinta sederhana ini tidak masalah tidak terlihat begitu apa namanya berat tapi kalau bagaimana kalau kita melakukan 10 Misalnya pembagian 10 kali, pembagian sampai 10 karakter, itu sudah kita melakukan pembagian fungsi sebanyak 1000 kali. Kita membagi karakter, kalau jumlah karakternya ada 20, kita bagi 2 setiap kombinasi.
itu sudah kita memanggil fungsi 1 juta kali jadi kalau kita punya 10 karakter 2, 3, 4, 5, 6, 7, 8, 9, 10 masing-masing putaran atau masing-masing iterasi kita membagi ini Hai yang membagi-bagi terus ya ini dibagi dengan ini dibandingkan ini dikombinasikan dengan ini kemudian ini dikombinasikan dengan ini terus bahkan Oke, snap. Itu sebanyak 10 karakter saja kita sudah melakukan pemanggilan fungsi sebanyak 1000 kali. Kita double 20 karakter, kita melakukan pemanggilan fungsi sebanyak 100 juta kali.
Nah 30 sudah tidak terhingga lagi, kita berapa kali? Memanggil fungsi Oleh sebab itu repetisi ini Punya big O yang cukup mahal sekali Yaitu eksponensial Dan eksponensial itu yang kita ingin hindarkan 2 pangkat N Jadi untuk inputnya Kita kalikan 2 2 kali saja Itu banyaknya fungsi yang harus kita panggil Dipangkatkan ya 2 pangkat 1000, 1 juta Nah, permasalahan-permasalahan seperti ini, rekursi-rekursi yang seperti ini yang harusnya kalian hindari. Kalau kalian sudah melakukan perhitungan di putaran sebelumnya, baiknya hasil dari putaran itu disimpan dengan teknik memoing tadi, memo.
Supaya nanti kalau di putaran berikutnya diperlukan hasil dari putaran sebelumnya, itu bisa langsung dipanggil tanpa harus melakukan kalkulasi ulang. Nah, itulah manfaat ketika kita belajar memoization dan dynamic programming. Jadi kesimpulan apa yang bisa kita ambil dari kompleksitas algoritm ini atau dari permasalahan string reconstruction ini.
ini merupakan cuma satu contoh permasalahan yang kalau kita mengerti algoritmi complexity itu bisa bisa apa namanya kita bisa mengerjakan atau membangun algoritma kita lebih baik dan lebih efisien sehingga menyimpan waktu save waktu dan save memori juga Hai nah eh ya harus kita hindarkan adalah greedy approach ya percobaan yang dirinya itu mencoba segala macam kombinasi soalnya kita coba segala macam kemungkinan ya tanpa memikirkan konsekuensi yang ada di langkah selanjutnya. Itulah yang biasa kita lakukan dengan greedy approach. Pada akhirnya akan menyelesaikan masalah, tapi dengan cost yang mahal karena greedy approach biasanya.
biasanya akan meledak secara eksponensial ya o2n kalau apa namanya penyelesaiannya secara grid approach karena grid approach membagi atau memecah-mecah string atau memecah-mecah sub masalah masalah-masalah yang kita punya itu secara rekursif dan tidak ada mekanisme menyimpan apa yang sudah dikerjakan sebelumnya. Makanya dia eksponensial, meledak secara eksponensial waktu dan spacenya. Nah, daripada kita melakukannya secara greedy atau greedy approach ini, ketika kita ingin menjelaskan masalah, pikirkan paradigma dengan pendekatan sub-problems.
Nah, di sini pemikiran atau paradigma pendekatan sub-problems ini, Itu mem Apa namanya memperlakukan masing-masing substring sebagai unit. Nah, kalau dia bekerja sebagai unit, masing-masing unit pasti punya prosesnya sendiri-sendiri. Sehingga kalau proses ini bisa kita pecah-pecah, proses ini bisa kita pecah-pecah, kalau ada proses yang berulang, kita tinggal mengambil hasil dari yang sudah dikerjakan.
Dan inilah yang kita sebut dengan bottom up efficiency. Karena kita dari bottom up, kita dari bawah ya, memecah-mecah permasalahan dari kecil. Secara apa namanya, secara kayak seperti main Lego ya, dari kecil. Kita susun, karena menyelesaikan masalah yang kecil-kecil ini pada akhirnya akan menyelesaikan masalah yang besar juga. Nah, untuk membantu kalian melakukan pemecahan masalah yang efisien ketika kalian dihadapkan pada permasalahan atau problems yang harus kalian selesaikan secara algoritm.
teknik yang satu secara mekanisme mekanisme yang terstruktur sebagai komputer juga bisa mengerjakannya ajukan pertanyaan-pertanyaan ini Apakah saya bisa membagi permasalahan permasalahan ya itu secara Bentuk-bentuk yang kecil Dalam bentuk-bentuk yang kecil Dan apa hasilnya Ketika saya menyelesaikan permasalahan saya yang kecil Apakah Penyelesaian masalah yang kecil ini Atau sub-problem yang kecil tadi Itu mendukung penyelesaian masalah yang lebih besar Itu yang ada di pertanyaan kedua Apakah menyelesaikan masalah yang kecil tadi Atau sub-problem yang kecil tadi Bisa membantu saya untuk Menyelesaikan masalah yang lebih Lebih besar lagi Itu kita kenal dengan bottom up approach Nah pada akhirnya Apakah menyelesaikan masalah yang Kecil-kecil itu Dapat membantu saya Menyelesaikan Atau menghasilkan solusi untuk Permasalahan yang lebih besar Kalau kita bisa menjawab pertanyaan-pertanyaan ini Itu berarti Kita sudah dilatih untuk berpikir Dalam menyelesaikan permasalahan yang besar Dengan membagi-bagi permasalahan yang Bermasalah yang kecil-kecil Dan secara Kehidupan kita sehari-hari pun Ketika kita dihadapkan pada masalah Cobalah untuk Sedikit Apa namanya Sedikit berpikir Untuk menyelesaikan masalah Sedikit demi sedikit. Karena penyelesaian masalah yang sedikit tentu lebih mudah daripada kita langsung menyelesaikan keseluruhan masalah. Penyelesaian misalnya kita punya masalah sebesar ilustrasinya inilah. Ada baiknya kita selesaikan sedikit dulu.
mungkin bagian sini kita selesaikan sehingga terhisah memang masih banyak tapi kalau kita tahu kalau menyelesaikan permasalahan yang sedikit ini itu membantu saya untuk menyelesaikan keseluruhan permasalahan Pada akhirnya nanti Semua permasalahan yang saya hadapi itu Akan terselesaikan juga Karena saya sudah memulai dengan hal-hal yang kecil Pola pikir atau paradigma seperti ini Sebanyak sekali dilakukan ketika kita Mengimplementasi aplikasi Misalnya spell checker Mengecek spelling Atau NLP Aplikasi AI Yang NLP Salam Kalau ada autocorrect, aplikasi mengenai pencarian atau autocorrect, itu juga seringkali menggunakan paradigma berpikir yang demikian. Jadi mengenai memoization, berikan kembali. Inti dari memoization adalah kita mencoba untuk mengeliminasi algoritma yang bersifat rekursif.
Karena algoritma bersifat rekursif itu. ini, kalau tidak di handle secara tepat dia akan blast atau dia akan meledak secara eksponensial oleh sebab itu untuk menguranginya kita mencoba untuk memanfaatkan mengingatkan mekanisme memoization atau mengingat apa yang sudah dihitung sebelumnya atau di kalkulasi sebelumnya ya Nah apa yang sudah dikalkulasi sebelumnya itu agar dia tidak dilakukan berulang-ulang ya itu harus ada overlapping subproblems artinya subproblems yang sudah ada itu ya dia bersifat overlapping sehingga kalau kita sudah menyelesaikan satu Tidak perlu kita menyelesaikan atau menghapusnya melakukan proses yang sama kita hanya perlu mengambil hasil dari proses yang sudah dilakukan sebelumnya yang tentu saja ini berdampak ini tentu berdampak kalau rekursif algoritma dan overlapping sub-reform terlalu dipaksakan tanpa memoization akan mengakibatkan ineficiensi dalam melakukan proses secara algoritmik ya Oleh sebab itu, memoization kita lakukan. Dan biasanya kalau kita lihat dari algoritma yang ada di samping ini, prinsipnya secara sederhana, kalau misalnya kita punya fungsi, kalau misalnya kita sudah melihat kalkulasi yang sudah ada sebelumnya ya kita tinggal return atau mengembalikan hasil yang sudah dihitung sebelumnya tapi kalau memang belum atau not seen atau belum maka ya Kita lakukan komputasi. Proses komputasi bisa macam-macam.
Tergantung logika atau tergantung kalian bagaimana melakukan komputasi. Tergantung rumus atau formula-formula juga kan. Kalau sudah dilakukan komputasi, hasilnya disimpan ke... Kalau di sini ibaratnya tabel yang baru atau array atau list.
list atau array yang bersifat kalau ini sudah untuk kasus dua variable arraynya dua dimensi dua dimensi kita simpan resultnya atau hasil komputasinya lalu kita set kalau untuk Perhitungan dengan dua variable i dan j ini sudah pernah terlihat, sehingga kita kasih flag atau kita indikasikan sebagai yang sudah dihitung. Lalu kita kembalikan nilai result. Pada putaran berikutnya, fungsi ini dipanggil lagi dan menemukan i dan j yang nilainya sama, sehingga sudah dilihat dia akan mengembalikan hasil tanpa harus melakukan komputasi ulang lagi.
kasus kita ini biasanya kita melakukan perhitungan dengan dua variabel. Oleh sebab itu, dua variabel ini kita biasa simpan dalam tabel yang bersifat dua dimensi. Kalau kalian perhitungannya dengan dimensi yang lebih tinggi, mungkin kalian harus menyimpannya dalam tempat penyimpanan 2 atau 3 dimensi. Pendefinisian dimensi itu sudah gampang. Kalau ini 2 dimensi, kalau 3 dimensi tinggal ditambahkan.
D misalnya, I, J. Hai kak misalnya ya artinya nanti dia akan dilihat kalau kalian menggambarnya dalam sumbu ke apa namanya kartesius ada X Y Z yang lalu titiknya dimana Kalau 3 dimensi. Kalau 4 dimensi bisa juga. 5 dimensi tidak apa-apa.
Hanya kita tidak bisa menggambarkan lebih dari 3 dimensi. Nah itu intinya dari sini. checking for previously computed results itu sama artinya ketika kita melakukan pengecekan apakah sudah dihitung atau sudah terlihat sebelumnya kalau sudah, ya tidak usah dihitung hanya kembalikan hasilnya ketika kita mengimplementasikan memoization ada beberapa hal yang harus diperhatikan yang pertama pengguna Oh penggunaan cache karena dia menyimpan hasil sementara menyimpan hasil perhitungan penggunaan cache sangat penting terutama ketika kalian ingin menyimpan hasil perhitungan secara sementara bukan permanen kalau penyimpanan data sementara ini terlalu berlebihan itu cenderung akan menyebabkan salah implementasi karena prosesnya juga akan sangat, prosesnya juga akan apa namanya mengurangi performance, kalau case-nya sudah lebih besar Jadi kalau misalnya memang dalam komputasi yang lama, yang berulang-ulang dan hasilnya itu banyak, sebaiknya kalau tidak diakses sesering mungkin hasil yang sudah dihitung.
dihitung sehingga simpan permanen jangan simpan di cash kemudian overhead of storage kalau misalnya penyimpanan yang tidak teratur karena kalian harus menyimpan hasil dari yang sudah dihitung sebelumnya kan ya Nah kalau penyimpanan tidak teratur dan tidak diukur itu akan menyebabkan overhead of storage Nah, pada kasus-kasus tertentu memang memoization biasanya tidak dilakukan. Mungkin karena permasalahan yang terlalu sederhana sehingga tidak memerlukan post. proses memoisin asri memosisi memosisi ya tapi kalau itu adalah kasus-kasus yang tidak memerlukan memosisi jens kalau kasus yang kita sebelumnya di memecahkan apa namanya kalau kasus memecahkan karakter memisah-misahkan karakter ya gini memisah-misahkan karakter Ups Hai misalkan misalkan karakter terus kita bandingkan kalau karakternya cuman misalnya ada 20 ya saya kira perhitungan pemanggilan fungsi selama satu juta kali juga tidak terlihat bedanya Hai tapi kalau misalnya dah kalau untuk kasus seperti ini ya mungkin tidak harus menggunakan memorization memorization tapi kalau n-nya bertambah kalau kalian lihat permasalahan kalian itu apa namanya membutuhkan perhitungan yang membutuhkan perhitungan yang cukup signifikan maka itulah memoization tapi kalau perhitungannya atau kalkulasinya tidak memerlukan komputasi artinya komputasinya masih bisa di handle dan tidak terlalu berbeda jauh dengan tidak melakukan memoization tidak usah menggunakan memoization jadi per kasus-per kasus tergantung input data kalian Hai namasi dalam emolisi sion berpengalaman masih dalam emolisi sion perhatikan ya apa namanya langkah-langkahnya untuk kita melakukan memorization pastikan total jumlah dari supra belum sih yang kalian punya ini karena masing-masing subproblem ketika di dilakukan penyelesaiannya itu pasti akan memakan waktu juga Hai ya makan waktu atau makan time jadi kalian ukur waktu persa problemnya itu apa namanya menghabiskan berapa waktu misalnya eh opsi eh eh eh eh sup problems Subproblem 1 diselesaikan dalam waktu 5 detik. Misalnya, subproblem 2 diselesaikan dalam waktu 7 detik.
Subproblem 3 dilakukan dalam waktu 8 detik. Misalnya, ya. Nah, total dari... dari apa yang sudah dilakukan ini ya itu adalah total misalnya jadi totalnya 18 20 detik 20 seconds terdapat total waktu yang dibutuhkan untuk masing-masing subproblems menyelesaikan masalahnya yang artinya sama saja dengan kalau memang subproblems 1, 2, 3 ini merupakan kombinasi dari problems yang kalian punya atau permasalahan yang ingin kalian selesaikan berarti kalian bisa menganggap kalau batas ketika kita harus menyelesaikan permasalahan itu 20 detik algoritma kita berjalan itu adalah total time dari kompleksitas memoisation akan berguna ketika kalau ada subproblems nomor 4, yang mana membutuhkan kalkulasi dari subproblems 2 dan subproblems 3, otomatis kalian tidak perlu melakukan ini lagi, penjumlahan 15 detik lagi ya kalian cukup mengambil cukup mengambil hasilnya, ya mungkin kalau mengambil hasil cuma membutuhkan waktu 1 detik sehingga totalnya jadi 21 detik ya, kalau kalian harus melakukan Perhitungan lagi, ya totalnya ditambah 15 lagi, jadi 35 detik. Itu yang membuat memoization lebih bermanfaat untuk kasus-kasus tersebut.
Pastikan benchmark kalian untuk masing-masing subproblems dihitung total kompleksitasnya berapa. Lalu apakah bermanfaatkah kalau kita melakukan atau mengingat hasil dari perhitungan ini. Hai nah masih saja berulangi aja untuk slide sini dynamic programming karena kalian sudah menjawabkan Pak sekarang sudah jelaskan apa itu dynamic programming ilustrasinya sama ya kalau memuai itu kristi notes tapi kalau dynamic programming gabungan seperti mengingat stiknot sini dalam bentuk saya contekan ya ada banyak stikin Ops nya ya semata-matanya itu dilakukan karena kelemahan dari sebuah rekursi yang time complexity-nya sangat eksponensial kalau kita tadi sudah melihat bagaimana kita memperkenalkan tabel untuk menyimpan hasil perhitungan dari tabel dua dimensi kadang tiga dimensi untuk menyimpan hasil setidaknya dua variabel yang harus kita hitung komputasinya Jadi dari apa namanya Kelemahan dari sebuah rekursi Kita mencoba untuk melakukan sesuatu lebih efisien lagi Supaya bisa mengalahkan atau bisa mengatasi permasalahan dari kelemahan dari rekursi ini Time complexity analysis analisis disini kita juga diajak untuk menganalisa time complexity dengan membandingkan Bagaimana kalau kita menggunakan rekursi time complexity nya bagaimana yaitu eksponensial ya dan time complexity ketika kita melakukan dynamic programming yang mana kalau kita lihat tadi lebih efisien Oke Nah, kalau kita bisa menerapkan pola pikir atau paradigma dynamic programming tersebut, yang sub-problems itu diharapkan untuk permasalahan-permasalahan selanjutnya, itu bisa kita teliti mana yang harus kita perbaiki dan mana yang bisa kita kembangkan atau scalability-nya lebih mungkin.
Hai yang hanya simpulan saja mengenai dynamic programming tadi contoh kasusnya kita memecah atau di mecah-mecah karakter-karakter untuk mendapatkan maksud yang yang untuk mendapatkan istilahnya strings yang mempunyai makna dengan menerapkan spasi-spasi rasa kalau ini ya pineapple kita bisa pecahkan disini pineapple pemecahannya mungkin bisa dilihat ada kata pen ada kata apple ada kata pen ada kata apple juga atau bisa kita ambil pineapple sebagai satu kata karakter satu string pen dan Apple. Ada tiga jadi bisa dibagi menjadi empat, sorry, empat apa namanya string yang bermakna. Satu, dua, tiga, empat.
Atau bisa kita bagi menjadi satu, dua, tiga string yang bermakna. Nah pemacaan-pemacaan itu menceratkan string manipulasi, string manipulation, dan penggunaan dictionary atau referensi untuk menemukan kata-kata yang bermakna tadi. f table f table itu yang kita harus simpan point yang mana kita harus simpan kalau kita memencangkannya disini kita menyimpan index dari start point dan finish point atau end point dari bagian pertama kemudian start point dan finish point dari bagian kedua start point dari finish point ke bagian ketiga itu semuanya mekanismenya diatur di dalam ekran.
f table recovery words itu mekanisme dimana kita harus bukan memperbaiki sebenarnya seperti menggabung-gabungkan kata supaya ditemukan makna yang supaya ditemukan kalau string itu mempunyai makna Hai nah kemudian terakhir sebagai kesimpulan ketika kita mempelajari apa namanya programming programming tadi memulainya dengan pengenalan akan linear programming karena ini biasanya terjadi di berbagai macam domain atau berbagai macam bidang studi termasuk finansial atau finance atau biologi kalau biologi itu menghitung rumus-rumus apa namanya banyak sekali matematik di biologi untuk menghitung banyak sekali misalnya risiko atau model-model bagaimana perkembang biakan bakteri misalnya daripada kita melakukan percobaan dengan bakteri yang sebenarnya, kita bisa melakukan simulasi, yang mana simulasi itu melibatkan perhitungan matematis bagaimana bakteri satu memecah belah atau berkembang biak terhadap lingkungan sekitar Atau scheduling atau penjatualan untuk menyelesaikan permasalahannya Nah itu kita biasanya temukan di permasalahan linear programming Hai nah ini program tersebut ya kalau kita istrinya kodify kodify ke dalam algoritma seperti kita bisa menyelesaikannya secara algoritmik dan juga sebagai komputer bisa selesaikannya Untuk mendapatkan algoritma yang efisien Kita bisa menerapkan teknik memoization Supaya time complexity-nya itu menjadi lebih rendah Tidak eksponensial Atau kita juga bisa melanjutkannya ke 2D Dynamic Programming. Kalau 2D Dynamic Programming ini memanfaatkan tabel 2 dimensi. Kalau dari contoh kasus kita, array atau list 2 dimensi. Sama seperti matrix sebenarnya, kalau kalian tulis dalam Python. 2 dimensi.
Hai kalau mau tiga dimensi pun silahkan tinggal tambahkan variabelnya saja atau 4 dimensi pun silahkan asalkan bisa ditambahkan apa namanya variabelnya nah penambahan dimensi ini semakin banyak tentu saja semakin lama perhitungannya jadi pastikan dapat dimensi yang paling kecil paling sedikit pada umumnya dalam praktek-praktek di lapangan itu biasanya menerapkan dua dimensi karena dua dimensi itu sudah cukup efisien untuk menekan waktu kalau dimungkinkan Hai menuju ke satu dimensi kalau kita bisa menemukan cara untuk menulis dynamic programming di space satu dimensi itu bisa mengurangi penggunaan memori yang kalau dua dimensi Cenderung kita menggunakannya untuk mengurangi waktu atau time. Jadi kalau satu dimensi, itu sudah bisa juga mengurangi space atau tempat atau memori. Nah, kalau sudah pada dynamic programming seperti ini, itu artinya algoritma kalian sudah sangat efisien, karena sudah bisa menekan time complexity dan juga menekan space complexity. Nah, begitu materi yang bisa disampaikan mengenai programming ini.