Algoritma
Introduced| English | Bahasa Indonesia |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritma |
| flowchart/ˈfləʊtʃɑːt/ | flowchart |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocode |
| tracing/ˈtreɪsɪŋ/ | pelacakan |
| binary search/ˈbaɪnəri sɜːtʃ/ | pencarian biner |
| linear search/ˈlɪnɪə sɜːtʃ/ | pencarian linear |
| efficiency/ɪˈfɪʃənsi/ | efisiensi |
Sebutkan input mana yang harus ditangani prosedur
- Algoritma menggambarkan langkah-langkah yang tidak ambigu untuk suatu tugas. Prosedur yang memecahkan tugas terbatas yang dinyatakan harus berhenti dan memberikan hasil yang benar untuk setiap input yang diizinkan.
- Jejak sukses pada satu input menunjukkan kasus itu, bukan pembuktian untuk semua input. Kasus batas dan input kosong dapat mengungkapkan kesalahan yang dilewati contoh biasa.
Manakah yang diperlukan agar suatu urutan langkah menjadi algoritma? Pilih semua yang berlaku.
Prosedur yang menyelesaikan tugas finite yang stated memerlukan langkah-langkah yang tidak ambigu, hasil yang benar, dan terminasi pada input yang diizinkan. Pseudocode dan flowchart adalah representasi, bukan persyaratan untuk menggunakan bahasa pemrograman tertentu.
Representasikan pilihan dan pembaruan dengan jelas
- Diagram alir menggunakan berlian keputusan, persegi panjang proses, jajar genjang input/keluaran, dan terminal mulai/berhenti, terhubung oleh panah aliran terarah.
- Pseudokode menggambarkan langkah-langkah tanpa memerlukan satu bahasa implementasi. Nyatakan arti penugasan, asal indeks, batas perulangan, dan kondisi percabangan sebelum melakukan jejak.
Cocokkan setiap bentuk bagan alir dengan artinya.
Gunakan persegi panjang proses, berlian keputusan, dan terminal mulai/berhenti sesuai yang diberikan; input/keluaran biasanya ditampilkan dengan jajar genjang. Label cabang keputusan dan arah aliran.
Catat nilai variabel aktual
- Jejak mengikuti pembaruan yang stated dalam urutan. Variabel sementara dapat mempertahankan nilai yang akan tertimpa jika tidak ada.
- Tampilkan low, high, middle, dan nilai dibandingkan untuk pencarian biner; tampilkan setiap variabel yang berubah untuk loop aritmatika. Hukum apa yang dilakukan prosedur, bukan hanya tujuannya.
Konvensi pencarian biner yang ditentukan. Gunakan batas inklusif nol-berbasis dan floor rata-ratanya untuk middle. Mencari 7 dalam [1,3,5,7,9,11] membandingkan indeks 2/nilai 5, indeks 4/nilai 9, lalu indeks 3/nilai 7. Jumlah perbandingan adalah tiga di bawah konvensi ini.
Linear terhadap pencarian biner
Pembagian dua mengalahkan pemeriksaan satu per satu, dan selisihnya semakin melebar seiring bertambahnya daftar.
Menggunakan batas inklusif nol-basis dan floor((low+high)/2), berapa banyak perbandingan yang digunakan pencarian biner untuk menemukan 7 dalam [1,3,5,7,9,11]?
Indeks tengah adalah 2, 4, kemudian 3, dengan nilai 5, 9, dan 7. Tiga perbandingan di bawah konvensi yang ditentukan.
Bandingkan kerja di bawah asumsinya
- Pencarian linear bisa berhenti lebih awal tetapi mungkin memeriksa semua item n. Pencarian biner berulang kali membagi dua rentang pencarian yang sudah diurutkan dan membutuhkan pembaruan batas yang konsisten.
- Efisiensi menggambarkan bagaimana kerja yang diperlukan berskala dengan ukuran input di bawah model yang didefinisikan. Mengurutkan terlebih dahulu memiliki biayanya sendiri; input yang tidak terurut tidak dapat mengandalkan jaminan pengurutan pencarian biner.
Untuk daftar berurutan satu juta item, kira-kira berapa banyak perbandingan nilai tengah yang bisa dibutuhkan pencarian biner dalam kasus terburuk?
Setiap perbandingan membagi dua jangkauan pencarian yang tersisa; sekitar 20 perbandingan cukup untuk satu juta item berurutan. Ini tidak termasuk biaya pengurutan sebelumnya.
Pencarian biner bekerja pada daftar yang tidak terurut, hanya lebih lambat.
Tanpa pengurutan yang diperlukan, membuang setengah dapat melewatkan item yang ada. Beberapa kasus mungkin kebetulan berhasil, tetapi kebenaran tidak terjamin.
Periksa nol dan indeks terakhir yang diizinkan. Lembar 4.4 examining loop penjumlahan menggunakan i kurang dari n, yang melewatkan suku terakhir. Jejak Euclidean-nya juga menjelaskan terminasi: setiap pembagi positif digantikan oleh sisa nonnegatif yang lebih kecil hingga nol tercapai.