Pada artikel ini, kita akan mempelajari mengapa setiap programmer harus mempelajari struktur data dan algoritma dengan bantuan contoh.
Artikel ini ditujukan bagi mereka yang baru saja mulai mempelajari algoritme dan bertanya-tanya seberapa besar dampaknya untuk meningkatkan keterampilan karier / pemrograman mereka. Ini juga untuk mereka yang bertanya-tanya mengapa perusahaan besar seperti Google, Facebook, dan Amazon mempekerjakan programmer yang sangat pandai mengoptimalkan Algoritma.
Apa itu Algoritma?
Secara informal, algoritme tidak lain adalah penyebutan langkah-langkah untuk memecahkan masalah. Mereka pada dasarnya adalah solusi.
Misalnya, algoritme untuk memecahkan masalah faktorial mungkin terlihat seperti ini:
Soal: Tentukan faktorial dari n
Inisialisasi fakta = 1 Untuk setiap nilai v dalam rentang 1 sampai n: Kalikan fakta dengan v fakta mengandung faktorial n
Di sini, algoritme ditulis dalam bahasa Inggris. Jika itu ditulis dalam bahasa pemrograman, kami akan menyebutnya kode sebagai gantinya. Berikut adalah kode untuk mencari faktorial sebuah bilangan dalam C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Pemrograman adalah tentang struktur data dan algoritma. Struktur data digunakan untuk menyimpan data sedangkan algoritma digunakan untuk menyelesaikan masalah dengan menggunakan data tersebut.
Struktur dan algoritme data (DSA) membahas solusi untuk masalah standar secara mendetail dan memberi Anda wawasan tentang seberapa efisien menggunakan masing-masing solusi. Ini juga mengajarkan Anda ilmu mengevaluasi efisiensi suatu algoritma. Ini memungkinkan Anda untuk memilih yang terbaik dari berbagai pilihan.
Penggunaan Struktur Data dan Algoritma untuk Membuat Kode Anda Dapat Disesuaikan
Waktu itu berharga.
Misalkan, Alice dan Bob mencoba memecahkan masalah sederhana untuk menemukan jumlah dari 10 11 bilangan asli pertama. Saat Bob menulis algoritme, Alice menerapkannya untuk membuktikan bahwa itu sesederhana mengkritik Donald Trump.
Algoritma (oleh Bob)
Inisialisasi jumlah = 0 untuk setiap bilangan asli n dalam rentang 1 hingga 1011 (inklusif): tambahkan n untuk menjumlahkan jumlah adalah jawaban Anda
Kode (oleh Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice dan Bob merasa gembira karena mereka dapat membangun sesuatu sendiri hampir dalam waktu singkat. Mari menyelinap ke ruang kerja mereka dan mendengarkan percakapan mereka.
Alice: Mari kita jalankan kode ini dan cari tahu jumlahnya. Bob: Saya menjalankan kode ini beberapa menit yang lalu tetapi masih belum menunjukkan hasilnya. Apakah ada yang salah?
Ups! Ada yang tidak beres! Komputer adalah mesin yang paling deterministik. Kembali dan mencoba menjalankannya lagi tidak akan membantu. Jadi mari kita analisis apa yang salah dengan kode sederhana ini.
Dua sumber daya paling berharga untuk program komputer adalah waktu dan memori .
Waktu yang dibutuhkan komputer untuk menjalankan kode adalah:
Waktu untuk menjalankan kode = jumlah instruksi * waktu untuk menjalankan setiap instruksi
Jumlah instruksi tergantung pada kode yang Anda gunakan, dan waktu yang dibutuhkan untuk mengeksekusi setiap kode tergantung pada mesin dan kompiler Anda.
Dalam kasus ini, jumlah instruksi yang dieksekusi (katakanlah x) adalah , yaitux = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Mari kita asumsikan bahwa komputer dapat menjalankan instruksi dalam satu detik (dapat bervariasi tergantung konfigurasi mesin). Waktu yang dibutuhkan untuk menjalankan kode di atas adalahy = 108
Waktu yang dibutuhkan untuk menjalankan kode = x / y (lebih dari 16 menit)
Apakah mungkin untuk mengoptimalkan algoritme sehingga Alice dan Bob tidak perlu menunggu selama 16 menit setiap kali menjalankan kode ini?
Saya yakin Anda sudah menebak metode yang benar. Jumlah N bilangan asli pertama diberikan dengan rumus:
Jumlah = N * (N + 1) / 2
Mengubahnya menjadi kode akan terlihat seperti ini:
int sum (int N) (return N * (N + 1) / 2;)
Kode ini dijalankan hanya dalam satu instruksi dan menyelesaikan tugas tidak peduli apa nilainya. Biarlah lebih besar dari jumlah total atom di alam semesta. Ini akan menemukan hasilnya dalam waktu singkat.
Waktu yang dibutuhkan untuk menyelesaikan masalah, dalam hal ini, adalah 1/y(yaitu 10 nanodetik). Ngomong-ngomong, reaksi fusi bom hidrogen membutuhkan waktu 40-50 ns, yang berarti program Anda akan selesai dengan sukses bahkan jika seseorang melempar bom hidrogen ke komputer Anda pada saat yang sama saat Anda menjalankan kode. :)
Catatan: Komputer mengambil beberapa instruksi (bukan 1) untuk menghitung perkalian dan pembagian. Saya telah mengatakan 1 hanya demi kesederhanaan.
Lebih lanjut tentang Skalabilitas
Skalabilitas adalah skala plus kemampuan yang berarti kualitas suatu algoritma / sistem untuk menangani masalah yang ukurannya lebih besar.
Pertimbangkan masalah menyiapkan ruang kelas dengan 50 siswa. Salah satu solusi paling sederhana adalah memesan kamar, mendapatkan papan tulis, beberapa kapur, dan masalahnya teratasi.
Tetapi bagaimana jika ukuran masalahnya bertambah? Bagaimana jika jumlah siswa bertambah menjadi 200?
Solusinya masih berlaku tetapi membutuhkan lebih banyak sumber daya. Dalam hal ini, Anda mungkin membutuhkan ruangan yang jauh lebih besar (mungkin teater), layar proyektor, dan pena digital.
Bagaimana jika jumlah siswanya bertambah menjadi 1000?
Solusi gagal atau menggunakan banyak sumber daya saat ukuran masalah meningkat. Artinya, solusi Anda tidak dapat diskalakan.
Lalu, apa solusi yang dapat diskalakan?
Consider a site like Khanacademy, millions of students can see videos, read answers at the same time and no more resources are required. So, the solution can solve the problems of larger size under resource crunch.
If you see our first solution to find the sum of first N natural numbers, it wasn't scalable. It's because it required linear growth in time with the linear growth in the size of the problem. Such algorithms are also known as linearly scalable algorithms.
Our second solution was very scalable and didn't require the use of any more time to solve a problem of larger size. These are known as constant-time algorithms.
Memory is expensive
Memory is not always available in abundance. While dealing with code/system which requires you to store or produce a lot of data, it is critical for your algorithm to save the usage of memory wherever possible. For example: While storing data about people, you can save memory by storing only their age not the date of birth. You can always calculate it on the fly using their age and current date.
Examples of an Algorithm's Efficiency
Here are some examples of what learning algorithms and data structures enable you to do:
Example 1: Age Group Problem
Problems like finding the people of a certain age group can easily be solved with a little modified version of the binary search algorithm (assuming that the data is sorted).
The naive algorithm which goes through all the persons one by one, and checks if it falls in the given age group is linearly scalable. Whereas, binary search claims itself to be a logarithmically scalable algorithm. This means that if the size of the problem is squared, the time taken to solve it is only doubled.
Suppose, it takes 1 second to find all the people at a certain age for a group of 1000. Then for a group of 1 million people,
- the binary search algorithm will take only 2 seconds to solve the problem
- the naive algorithm might take 1 million seconds, which is around 12 days
The same binary search algorithm is used to find the square root of a number.
Example 2: Rubik's Cube Problem
Imagine you are writing a program to find the solution of a Rubik's cube.
This cute looking puzzle has annoyingly 43,252,003,274,489,856,000 positions, and these are just positions! Imagine the number of paths one can take to reach the wrong positions.
Fortunately, the way to solve this problem can be represented by the graph data structure. There is a graph algorithm known as Dijkstra's algorithm which allows you to solve this problem in linear time. Yes, you heard it right. It means that it allows you to reach the solved position in a minimum number of states.
Example 3: DNA Problem
DNA is a molecule that carries genetic information. They are made up of smaller units which are represented by Roman characters A, C, T, and G.
Imagine yourself working in the field of bioinformatics. You are assigned the work of finding out the occurrence of a particular pattern in a DNA strand.
It is a famous problem in computer science academia. And, the simplest algorithm takes the time proportional to
(number of character in DNA strand) * (number of characters in pattern)
A typical DNA strand has millions of such units. Eh! worry not. KMP algorithm can get this done in time which is proportional to
(number of character in DNA strand) + (number of characters in pattern)
The * operator replaced by + makes a lot of change.
Considering that the pattern was of 100 characters, your algorithm is now 100 times faster. If your pattern was of 1000 characters, the KMP algorithm would be almost 1000 times faster. That is, if you were able to find the occurrence of pattern in 1 second, it will now take you just 1 ms. We can also put this in another way. Instead of matching 1 strand, you can match 1000 strands of similar length at the same time.
And there are infinite such stories…
Final Words
Generally, software development involves learning new technologies on a daily basis. You get to learn most of these technologies while using them in one of your projects. However, it is not the case with algorithms.
Jika Anda tidak mengetahui algoritme dengan baik, Anda tidak akan dapat mengidentifikasi apakah Anda dapat mengoptimalkan kode yang Anda tulis sekarang. Anda diharapkan untuk mengenal mereka sebelumnya dan menerapkannya jika memungkinkan dan kritis.
Kami secara khusus berbicara tentang skalabilitas algoritme. Sistem perangkat lunak terdiri dari banyak algoritma semacam itu. Mengoptimalkan salah satu dari mereka mengarah ke sistem yang lebih baik.
Namun, penting untuk dicatat bahwa ini bukan satu-satunya cara untuk membuat sistem dapat diskalakan. Misalnya, teknik yang dikenal sebagai komputasi terdistribusi memungkinkan bagian independen dari sebuah program untuk dijalankan ke beberapa mesin bersama-sama sehingga membuatnya lebih skalabel.
