Struktur Data - Dasar-dasar Algoritma

Algoritma adalah prosedur langkah-demi-langkah, yang mendefinisikan sekumpulan instruksi yang akan dijalankan dalam urutan tertentu untuk mendapatkan keluaran yang diinginkan. Algoritme umumnya dibuat secara independen dari bahasa yang mendasarinya, yaitu algoritme dapat diimplementasikan di lebih dari satu bahasa pemrograman.

Dari sudut pandang struktur data, berikut adalah beberapa kategori penting dari algoritma -

Search - Algoritma untuk mencari item dalam struktur data.
Sort - Algoritma untuk mengurutkan item dalam urutan tertentu.
Insert - Algoritma untuk memasukkan item ke dalam struktur data.
Update - Algoritma untuk memperbarui item yang ada dalam struktur data.
Delete - Algoritma untuk menghapus item yang ada dari struktur data.

Karakteristik Algoritma

Tidak semua prosedur bisa disebut algoritma. Algoritme harus memiliki karakteristik berikut -

Unambiguous- Algoritma harus jelas dan tidak ambigu. Setiap langkah (atau fase), dan masukan / keluarannya harus jelas dan hanya mengarah pada satu makna.
Input - Algoritme harus memiliki 0 atau lebih input yang terdefinisi dengan baik.
Output - Algoritme harus memiliki 1 atau lebih keluaran yang terdefinisi dengan baik, dan harus cocok dengan keluaran yang diinginkan.
Finiteness - Algoritme harus dihentikan setelah sejumlah langkah terbatas.
Feasibility - Harus layak dengan sumber daya yang tersedia.
Independent - Algoritme harus memiliki petunjuk langkah demi langkah, yang harus independen dari kode pemrograman apa pun.

Bagaimana Cara Menulis Algoritma?

Tidak ada standar yang didefinisikan dengan baik untuk penulisan algoritma. Sebaliknya, ini tergantung pada masalah dan sumber daya. Algoritma tidak pernah ditulis untuk mendukung kode pemrograman tertentu.

Seperti yang kita ketahui bahwa semua bahasa pemrograman berbagi konstruksi kode dasar seperti loop (do, for, while), flow-control (if-else), dll. Konstruksi umum ini dapat digunakan untuk menulis algoritme.

Kami menulis algoritme secara selangkah demi selangkah, tetapi tidak selalu demikian. Penulisan algoritme adalah proses dan dijalankan setelah domain masalah didefinisikan dengan baik. Artinya, kita harus mengetahui domain masalahnya, untuk itu kita sedang merancang solusinya.

Contoh

Mari kita coba belajar penulisan algoritma dengan menggunakan sebuah contoh.

Problem - Rancang algoritma untuk menambahkan dua angka dan menampilkan hasilnya.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Algoritme memberi tahu pemrogram cara membuat kode program. Atau, algoritme dapat ditulis sebagai -

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Dalam desain dan analisis algoritma, biasanya metode kedua digunakan untuk mendeskripsikan suatu algoritma. Ini memudahkan analis untuk menganalisis algoritme yang mengabaikan semua definisi yang tidak diinginkan. Dia dapat mengamati operasi apa yang digunakan dan bagaimana prosesnya mengalir.

Penulisan step numbers, bersifat opsional.

Kami merancang algoritme untuk mendapatkan solusi dari masalah tertentu. Sebuah masalah dapat diselesaikan dengan lebih dari satu cara.

Karenanya, banyak algoritma solusi dapat diturunkan untuk masalah tertentu. Langkah selanjutnya adalah menganalisis algoritma solusi yang diusulkan tersebut dan menerapkan solusi terbaik yang sesuai.

Analisis Algoritma

Efisiensi suatu algoritma dapat dianalisis pada dua tahap yang berbeda, sebelum implementasi dan setelah implementasi. Mereka adalah sebagai berikut -

A Priori Analysis- Ini adalah analisis teoritis dari suatu algoritma. Efisiensi algoritme diukur dengan mengasumsikan bahwa semua faktor lain, misalnya, kecepatan prosesor, adalah konstan dan tidak berpengaruh pada implementasi.
A Posterior Analysis- Ini adalah analisis empiris dari suatu algoritma. Algoritma yang dipilih diimplementasikan dengan menggunakan bahasa pemrograman. Ini kemudian dieksekusi pada mesin komputer target. Dalam analisis ini, statistik aktual seperti waktu dan ruang berjalan yang diperlukan, dikumpulkan.

Kita akan belajar tentang analisis algoritma apriori . Analisis algoritme berkaitan dengan pelaksanaan atau waktu berjalan berbagai operasi yang terlibat. Waktu berjalan suatu operasi dapat didefinisikan sebagai jumlah instruksi komputer yang dijalankan per operasi.

Kompleksitas Algoritma

Seharusnya X adalah sebuah algoritma dan n adalah ukuran data masukan, waktu dan ruang yang digunakan oleh algoritma X adalah dua faktor utama yang menentukan efisiensi X.

Time Factor - Waktu diukur dengan menghitung jumlah operasi kunci seperti perbandingan dalam algoritma pengurutan.
Space Factor - Ruang diukur dengan menghitung ruang memori maksimum yang dibutuhkan oleh algoritma.

Kompleksitas suatu algoritma f(n) memberikan waktu berjalan dan / atau ruang penyimpanan yang dibutuhkan oleh algoritme dalam hal n sebagai ukuran data masukan.

Kompleksitas Ruang

Kompleksitas ruang dari suatu algoritma merepresentasikan jumlah ruang memori yang dibutuhkan oleh algoritma dalam siklus hidupnya. Ruang yang dibutuhkan oleh algoritme sama dengan jumlah dari dua komponen berikut -

Bagian tetap yang merupakan ruang yang diperlukan untuk menyimpan data dan variabel tertentu, yang tidak bergantung pada ukuran masalah. Misalnya, variabel dan konstanta sederhana yang digunakan, ukuran program, dll.
Bagian variabel adalah ruang yang dibutuhkan oleh variabel, yang ukurannya bergantung pada ukuran masalah. Misalnya, alokasi memori dinamis, ruang tumpukan rekursi, dll.

Kompleksitas spasi S (P) dari setiap algoritma P adalah S (P) = C + SP (I), di mana C adalah bagian tetap dan S (I) adalah bagian variabel dari algoritma, yang bergantung pada karakteristik instans I. Berikut adalah contoh sederhana yang mencoba menjelaskan konsep -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Di sini kita memiliki tiga variabel A, B, dan C dan satu konstanta. Karenanya S (P) = 1 + 3. Sekarang, ruang bergantung pada tipe data dari variabel yang diberikan dan tipe konstanta dan itu akan dikalikan sesuai.

Kompleksitas Waktu

Kompleksitas waktu suatu algoritme merepresentasikan jumlah waktu yang dibutuhkan algoritme untuk berjalan hingga selesai. Persyaratan waktu dapat didefinisikan sebagai fungsi numerik T (n), di mana T (n) dapat diukur sebagai jumlah langkah, asalkan setiap langkah menggunakan waktu yang konstan.

Sebagai contoh, diperlukan penambahan dua bilangan bulat n-bit nLangkah. Akibatnya, waktu komputasi total adalah T (n) = c ∗ n, di mana c adalah waktu yang dibutuhkan untuk penambahan dua bit. Di sini, kami mengamati bahwa T (n) tumbuh secara linier dengan bertambahnya ukuran input.