Istilah K1 · Struktur Data dan Algoritma

90 dari 90 istilah

• __getitem__

  Metode khusus yang dipanggil Python untuk daftar[i], yaitu daftar.__getitem__(i). Menimpanya memungkinkan kelas mencatat setiap pembacaan elemen, seperti DaftarDihitung.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• __hash__

  Metode khusus yang dipanggil hash(x) dan dipakai dict serta set untuk memilih ember. Objek yang sama menurut __eq__ wajib punya hash sama; cara termudah, hash tuple berisi bagian yang dibandingkan.

  Contoh: Titik mengembalikan hash((self.x, self.y)).

  Dipelajari di Modul 06 · Tabel hash

• __lt__

  Metode khusus yang dipanggil Python untuk a < b, yaitu a.__lt__(b). sorted, min, heapq, dan bisect hanya memakai <, jadi kelas yang punya __lt__ bisa diurutkan dan dicari.

  Dipelajari di F1 · Modul 12 · Kelas dan dataclass

• @cache

  Dekorator dari functools yang memberi fungsi memo otomatis: jawaban untuk setiap argumen dihitung sekali, lalu diambil dari memo. Argumennya harus bisa menjadi kunci dictionary, dan memonya tidak pernah dikosongkan sendiri.

  Contoh: dengan @cache, fib(100) menghitung 101 jawaban saja.

  Dipelajari di Modul 03 · Rekursi dan induksi

• akar

  Simpul paling atas sebuah pohon, satu-satunya simpul tanpa induk. Semua jalur dimulai dari akar. Di heap min, akar berisi nilai terkecil.

  Contoh: di pohon menu, Menu adalah akar dengan anak Makanan dan Minuman.

  Dipelajari di Modul 10 · Pohon dan pohon pencarian biner

• algoritma rakusjuga: rakus, greedy

  Algoritma yang di setiap langkah mengambil pilihan yang tampak terbaik saat itu, tanpa pernah menengok kembali. Cepat dan sederhana, tetapi hanya benar untuk soal tertentu, dan kebenarannya harus dibuktikan.

  Contoh: memilih tugas antar yang selesai paling awal memberi jadwal terbanyak; "rumah terdekat dulu" tidak selalu memberi rute terpendek.

  Dipelajari di Modul 15 · Rakus dan backtracking

• amortisasijuga: analisis amortisasi

  Cara menghitung biaya rata-rata per operasi atas satu deret operasi di kasus terburuk. Satu operasi boleh mahal sesekali, asalkan total semuanya tetap kecil.

  Contoh: append kadang menyalin seluruh list, tetapi n kali append menyalin kurang dari 2n elemen, jadi O(1) amortisasi per append.

  Dipelajari di Modul 04 · Array dinamis dan list berantai

• antreanjuga: queue, FIFO

  Wadah dengan aturan "pertama masuk, pertama keluar" (FIFO): elemen masuk di belakang dan keluar dari depan.

  Contoh: pesanan yang masuk lebih dulu diantar lebih dulu. BFS juga memakai antrean untuk menjelajah peta tingkat demi tingkat.

  Dipelajari di Modul 05 · Stack, queue, dan deque

• antrean prioritasjuga: priority queue

  Wadah yang selalu mengeluarkan elemen dengan prioritas paling tinggi lebih dulu, bukan yang paling lama menunggu. Biasanya dibuat dengan heap.

  Contoh: antrean pesanan yang selalu mengeluarkan pesanan dengan batas waktu paling dekat.

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• array dinamis

  Array yang bisa tumbuh: elemen disimpan di sel memori berdampingan dengan kapasitas lebih besar dari yang terpakai. Saat penuh, dibuat array baru berkapasitas dua kali lipat dan semua elemen disalin. list Python bekerja seperti ini.

  Contoh: sesudah 17 penambahan, kapasitasnya 32 dan total salinannya baru 31 elemen.

  Dipelajari di Modul 04 · Array dinamis dan list berantai

• backtracking

  Pencarian sistematis yang membangun solusi sepotong demi sepotong: pilih satu kemungkinan, jelajahi kelanjutannya secara rekursif, lalu batalkan pilihan itu dan coba kemungkinan berikutnya. Cabang yang pasti kalah boleh dipangkas.

  Contoh: mencoba semua urutan kunjungan R02, R07, dan R09 menghasilkan 6 rute.

  Dipelajari di Modul 15 · Rakus dan backtracking

• bagi-dan-taklukkanjuga: divide and conquer

  Pola algoritma tiga langkah: bagi masalah menjadi beberapa masalah sejenis yang lebih kecil, selesaikan masing-masing secara rekursif, lalu gabungkan jawabannya.

  Contoh: merge sort membelah list menjadi dua, mengurutkan setiap separuh, lalu menggabungkan dua hasil yang sudah terurut.

  Dipelajari di Modul 08 · Pengurutan efisien

• bangun_graf

  Fungsi proyek Kurir Makmur yang mengubah peta menjadi daftar ketetanggaan: graf[titik] adalah list pasangan (tetangga, jarak_m) yang terurut menurut id tetangga, dengan jalan dua arah dicatat dua kali.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• BFSjuga: penelusuran melebar, breadth-first search

  Cara menjelajah graf tingkat demi tingkat dengan antrean: titik awal, lalu semua tetangganya, lalu tetangga mereka yang belum dikunjungi. BFS menemukan rute dengan jalan paling sedikit, dalam O(V + E).

  Contoh: dari A, BFS menemukan B dan C berjarak 1, lalu D dan E berjarak 2.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• bisect_left

  Fungsi modul bisect yang mencari, dengan pencarian biner, indeks pertama di list terurut yang elemennya tidak lebih kecil dari x. Sama dengan batas_bawah buatanmu sendiri.

  Contoh: bisect_left([10, 20, 20, 30], 20) bernilai 1.

  Dipelajari di Modul 09 · Pencarian biner dan dua penunjuk

• bisect_right

  Fungsi modul bisect yang mengembalikan indeks pertama di list terurut yang elemennya lebih besar dari x, yaitu posisi tepat sesudah semua elemen yang sama dengan x.

  Contoh: bisect_right([10, 20, 20, 30], 20) bernilai 3.

  Dipelajari di Modul 09 · Pencarian biner dan dua penunjuk

• bit_length

  Metode bilangan bulat yang mengembalikan banyak digit binernya. Untuk n ≥ 1, n.bit_length() - 1 sama dengan ⌊log₂ n⌋, tanpa galat pembulatan float.

  Contoh: (1000).bit_length() bernilai 10, karena 1000 dalam biner adalah 1111101000.

  Dipelajari di Modul 02 · Notasi asimtotik

• daftar ketetanggaanjuga: adjacency list

  Cara menyimpan graf: untuk setiap titik, simpan list titik yang bisa dicapai lewat satu sisi (tetangganya). Ruangnya O(V + E), hemat untuk graf yang sisinya sedikit. Kebalikannya matriks ketetanggaan, tabel V × V.

  Contoh: graf["W"] berisi [('S22', 60), ('S23', 90)]: dari warung ada jalan ke S22 (60 m) dan S23 (90 m).

  Dipelajari di Modul 12 · Graf 1: menjelajah

• DaftarDihitung

  Turunan list yang mencatat setiap pembacaan (dibaca) dan penulisan (ditulis) elemen. Tes K1 memakainya untuk memeriksa batas efisiensi, misalnya "paling banyak 2n pembacaan".

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• DAGjuga: directed acyclic graph

  Graf berarah tanpa siklus. Hanya graf seperti ini yang punya urutan topologis.

  Contoh: aturan persiapan nasi bungkus ("bungkus nasi" menunggu "masak nasi" dan "siapkan kotak") adalah DAG.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• daun

  Simpul pohon yang tidak punya anak.

  Contoh: di pohon menu, Teh, Kopi, dan Mi adalah daun, sedangkan Nasi bukan karena punya anak Goreng dan Uduk.

  Dipelajari di Modul 10 · Pohon dan pohon pencarian biner

• deque

  Kelas dari collections untuk antrean dua ujung: menambah dan mengambil di depan maupun belakang sama-sama O(1). Pilihan tepat untuk antrean, karena list.pop(0) harus menggeser semua elemen.

  Contoh: deque(maxlen=3) hanya menyimpan tiga titik terakhir yang dilewati kurir.

  Dipelajari di Modul 05 · Stack, queue, dan deque

• DFSjuga: penelusuran mendalam, depth-first search

  Cara menjelajah graf dengan masuk sedalam mungkin lewat satu tetangga, lalu mundur bila buntu dan mencoba tetangga berikutnya. Ditulis dengan rekursi atau tumpukan; O(V + E). Dipakai antara lain untuk mencari siklus dan kelompok titik yang saling terhubung.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• Dijkstrajuga: algoritma Dijkstra

  Algoritma rute terpendek untuk graf berbobot tanpa bobot negatif. Ia menyelesaikan titik satu per satu dari yang terdekat ke titik awal, memakai heap untuk mengambil yang terdekat; O((V + E) log V).

  Contoh: jarak terjauh dari warung di peta adalah R14, 1.580 m.

  Dipelajari di Modul 13 · Graf 2: jalur terpendek dan pohon rentang

• dua penunjukjuga: two pointers

  Teknik memakai dua indeks yang bergerak di list yang sama, misalnya satu dari kiri dan satu dari kanan, sehingga setiap langkah membuang satu kemungkinan. Sering mengubah O(n²) menjadi O(n).

  Contoh: mencari dua pesanan yang beratnya pas 5.000 g di list berat terurut: majukan kiri bila jumlahnya kurang, mundurkan kanan bila lebih.

  Dipelajari di Modul 09 · Pencarian biner dan dua penunjuk

• emberjuga: bucket

  Satu tempat penyimpanan di tabel hash, bernomor 0 sampai m − 1. Kunci masuk ke ember yang ditunjuk fungsi hash; kunci yang bertabrakan berbaris di ember yang sama.

  Contoh: dengan 5 ember, kunci 18, 23, 13, dan 8 semuanya masuk ember 3 karena sisa baginya oleh 5 sama-sama 3.

  Dipelajari di Modul 06 · Tabel hash

• faktor muatjuga: load factor, faktor beban

  Perbandingan banyak kunci dengan banyak ember, α = n/m: rata-rata isi satu ember. Selama α dijaga di bawah batas tertentu (misalnya 0,75), operasi tabel hash tetap O(1) rata-rata; bila lewat, tabel diperbesar.

  Contoh: 1.200 kunci di 1.600 ember memberi α = 0,75.

  Dipelajari di Modul 06 · Tabel hash

• fungsi hashjuga: hash

  Fungsi yang mengubah kunci menjadi bilangan bulat, lalu dipakai untuk memilih ember. Kunci yang sama harus selalu memberi hasil yang sama, dan kunci berbeda sebaiknya menyebar merata. Dua kunci berbeda di ember yang sama disebut tabrakan.

  Contoh: h(k) = k mod 7 menaruh resi 2026101700010 di ember 3.

  Dipelajari di Modul 06 · Tabel hash

• grafjuga: graph

  Kumpulan titik yang dihubungkan sisi; ditulis G = (V, E). Banyak titik disebut V dan banyak sisi E. Sisi boleh punya bobot, misalnya jarak dalam meter.

  Contoh: peta Kurir Makmur adalah graf: 62 titik (warung, simpang, rumah) dan 81 jalan sebagai sisi.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• graf berarahjuga: berarah, tak berarah, graf tak berarah

  Graf yang setiap sisinya hanya bisa dilalui satu arah, dari u ke v. Pada graf tak berarah, setiap sisi bisa dilalui dua arah.

  Contoh: peta kelurahan dicatat sebagai graf berarah; jalan dua arah menjadi dua sisi, sedangkan jalan satu arah S02 → S03 hanya satu.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• heapjuga: heap biner, heap min, heap maks

  Pohon biner lengkap yang disimpan di list, dengan aturan setiap induk tidak lebih besar dari anak-anaknya (heap min), jadi elemen terkecil selalu di indeks 0. Menambah dan mengambil yang terkecil O(log n). Heap maks kebalikannya.

  Contoh: [48, 112, 158, 171, 177, 190, 218, 220]; anak indeks i ada di 2i + 1 dan 2i + 2.

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• heapify

  Fungsi heapq yang menyusun ulang list biasa menjadi heap di tempat, dalam waktu O(n), lebih cepat daripada memasukkan elemen satu per satu.

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• heappop

  Fungsi heapq yang mengambil dan mengembalikan elemen terkecil (h[0]), lalu memperbaiki heap. O(log n). Heap kosong memunculkan IndexError.

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• heappush

  Fungsi heapq yang menambahkan elemen ke heap: ditaruh di akhir list, lalu naik sampai induknya tidak lebih besar. O(log n).

  Contoh: heapq.heappush(antrean, (batas_menit, id, pesanan)).

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• heapq

  Modul pustaka standar yang menjalankan heap min di atas list biasa. Fungsinya antara lain heappush, heappop, heapify, nsmallest, nlargest, dan merge. Untuk heap maks, simpan kunci negatif.

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• induksi matematikajuga: induksi, hipotesis induksi

  Cara membuktikan pernyataan P(n) untuk semua bilangan asli: buktikan basisnya (misalnya P(0)), lalu langkahnya: bila P(k) benar (hipotesis induksi), P(k + 1) juga benar. Induksi kuat boleh memakai semua P(j) dengan j ≤ k.

  Contoh: Menara Hanoi butuh 2ⁿ − 1 langkah, dibuktikan dengan induksi pada banyak cakram.

  Dipelajari di Modul 03 · Rekursi dan induksi

• insertion sort

  Pengurutan yang mengambil elemen satu per satu, lalu menggeser elemen-elemen lebih besar di kirinya ke kanan sampai tempatnya ketemu, seperti menyusun kartu di tangan. Θ(n²) di kasus terburuk, tetapi sangat cepat untuk data yang hampir terurut.

  Contoh: [29, 10, 14, 37, 13] menjadi [10, 13, 14, 29, 37] dalam empat putaran.

  Dipelajari di Modul 07 · Pengurutan dasar dan pembuktiannya

• invarian

  Pernyataan yang selalu benar pada titik-titik tertentu selama program berjalan, misalnya di awal setiap putaran atau sesudah setiap operasi. Invarian dipakai untuk membuktikan bahwa kode benar untuk semua masukan, bukan hanya yang dites.

  Contoh: pada pencarian biner batas bawah, semua indeks di kiri lo selalu berisi nilai yang lebih kecil dari x.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• invarian perulanganjuga: loop invariant

  Invarian yang benar setiap kali perulangan akan memulai satu putaran. Buktinya tiga bagian: benar sebelum putaran pertama (inisialisasi), tetap benar dari satu putaran ke putaran berikutnya (pemeliharaan), dan saat perulangan selesai memberi hasil yang diminta (terminasi).

  Contoh: "terbaik adalah indeks pertama nilai terkecil di daftar[0:k]".

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• jumlah awalanjuga: jumlah prefiks, prefix sum

  List yang menyimpan total berjalan: elemen ke-k berisi jumlah k elemen pertama data. Sesudah disiapkan sekali, jumlah potongan mana pun didapat dengan satu pengurangan.

  Contoh: nilai pesanan tiga hari [5, 3, 8] punya jumlah awalan [0, 5, 8, 16]; total hari kedua dan ketiga adalah 16 − 5 = 11.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• kasus dasarjuga: base case

  Bagian fungsi rekursif yang menjawab masukan terkecil secara langsung, tanpa memanggil dirinya lagi. Tanpa kasus dasar, rekursi tidak pernah berhenti.

  Contoh: pada Fibonacci, fib(0) = 0 dan fib(1) = 1 adalah kasus dasar.

  Dipelajari di Modul 03 · Rekursi dan induksi

• kasus rata-rata

  Rata-rata banyak langkah untuk semua masukan berukuran n, dengan sebuah anggapan tentang seberapa sering setiap masukan muncul. Hasilnya hanya berlaku selama anggapannya benar.

  Contoh: bila angka yang dicari pasti ada dan setiap posisi sama mungkinnya, pencarian satu per satu butuh rata-rata (n + 1)/2 perbandingan: 101/2 untuk n = 100.

  Dipelajari di Modul 02 · Notasi asimtotik

• kasus terburukjuga: worst case

  Banyak langkah terbesar yang mungkin untuk semua masukan berukuran n. Kebalikannya kasus terbaik, banyak langkah terkecil. Kasus terburuk paling sering dipakai karena menjadi jaminan untuk setiap masukan.

  Contoh: mencari angka di list 100 elemen satu per satu butuh 100 perbandingan bila angkanya di belakang atau tidak ada, dan 1 bila di depan.

  Dipelajari di Modul 02 · Notasi asimtotik

• knapsack 0/1juga: knapsack

  Soal memilih barang (diambil utuh atau tidak sama sekali) agar total nilainya terbesar tanpa melewati kapasitas. Diselesaikan dengan pemrograman dinamis dalam O(n · C), dengan C kapasitas.

  Contoh: tas motor 4.000 g: mengambil pesanan 3 dan 4 memberi Rp85.000, lebih baik dari pilihan rakus Rp75.000.

  Dipelajari di Modul 14 · Pemrograman dinamis

• kompleksitas ruangjuga: ruang tambahan

  Banyak memori tambahan yang dipakai algoritma di luar masukannya, ditulis dengan notasi O seperti waktu. Salinan tersembunyi ikut dihitung.

  Contoh: daftar[1:] dan sorted(daftar) membuat list baru, jadi butuh O(n) ruang; reversed(daftar) tidak.

  Dipelajari di Modul 02 · Notasi asimtotik

• lambda

  Cara menulis fungsi kecil tanpa nama dalam satu ekspresi, sering untuk key=. lambda p: p["berat_g"] sama dengan fungsi yang mengembalikan berat pesanan p.

  Dipelajari di F1 · Modul 07 · List dan tuple

• leksikografisjuga: urutan leksikografis

  Urutan seperti di kamus: bandingkan elemen pertama; bila sama, elemen kedua; dan seterusnya. Urutan yang lebih pendek tetapi sama di awal datang lebih dulu. Python membandingkan list, tuple, dan string dengan cara ini.

  Contoh: ['W', 'R16', 'R11'] lebih kecil dari ['W', 'R16', 'R22'] karena 'R11' < 'R22'.

• list berantaijuga: linked list, list berantai tunggal, list berantai ganda

  Struktur yang menyimpan setiap elemen di simpul tersendiri; setiap simpul menunjuk simpul berikutnya. Menyisip di depan cepat, tetapi membaca elemen ke-i harus berjalan i langkah. Versi ganda juga menyimpan rujukan ke simpul sebelumnya.

  Contoh: riwayat antar R07 → R11 → R24, dengan simpul R24 menunjuk None.

  Dipelajari di Modul 04 · Array dinamis dan list berantai

• logaritmajuga: log₂

  log₂ n adalah pangkat yang membuat 2 menjadi n, atau kira-kira berapa kali n bisa dibagi dua sampai tersisa 1. Tumbuhnya sangat lambat: log₂ 1.000 ≈ 10 dan log₂ 1.000.000 ≈ 20.

  Contoh: pencarian biner di 1.000 jadwal hanya butuh 10 pembacaan karena setiap langkah membuang separuh calon.

• memoisasijuga: memo

  Teknik menyimpan jawaban setiap submasalah di dictionary (memo) saat pertama kali dihitung, lalu mengembalikannya langsung bila ditanya lagi. Syaratnya: fungsinya selalu memberi jawaban sama untuk argumen sama, dan argumennya bisa menjadi kunci dictionary.

  Contoh: dengan memo, fib(100) hanya butuh 199 panggilan, bukan miliaran.

  Dipelajari di Modul 03 · Rekursi dan induksi

• merge sort

  Pengurutan bagi-dan-taklukkan: belah list menjadi dua bagian sama besar, urutkan masing-masing secara rekursif, lalu gabungkan dua list terurut itu. Selalu Θ(n log n) dan stabil, tetapi butuh Θ(n) ruang tambahan.

  Contoh: [38, 27, 43, 3, 9, 82, 10] dibelah sampai tinggal satu elemen, lalu digabung naik menjadi [3, 9, 10, 27, 38, 43, 82].

  Dipelajari di Modul 08 · Pengurutan efisien

• model biayajuga: operasi dominan

  Kesepakatan untuk mengukur kecepatan dengan menghitung langkah, bukan detik: satu perbandingan, satu penjumlahan, atau satu akses elemen dihitung satu langkah. Biasanya cukup menghitung operasi dominan, yaitu operasi yang paling sering dijalankan.

  Contoh: memeriksa semua pasangan 1.000 elemen butuh 499.500 perbandingan di komputer mana pun.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• muat_peta

  Fungsi proyek Kurir Makmur yang membaca peta.json dan mengembalikan dictionary berisi titik, jalan, dan pesanan.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• notasi asimtotik

  Cara menuliskan bentuk pertumbuhan banyak langkah saat ukuran masukan n membesar, dengan membuang konstanta dan suku kecil. Tiga notasinya: O (batas atas), Ω (batas bawah), dan Θ (keduanya sekaligus).

  Contoh: 3n² + 10n + 5 langkah ditulis Θ(n²): menggandakan n membuat kerjanya sekitar empat kali.

  Dipelajari di Modul 02 · Notasi asimtotik

• notasi Ojuga: Big-O, O besar

  f(n) = O(g(n)) berarti f tidak tumbuh lebih cepat dari g: ada konstanta c dan n₀ sehingga f(n) ≤ c · g(n) untuk setiap n ≥ n₀. O hanya batas atas, bukan "persis", dan bukan berarti kasus terburuk.

  Contoh: 5n = O(n²) benar, walaupun batasnya tidak tajam.

  Dipelajari di Modul 02 · Notasi asimtotik

• notasi Θjuga: Theta, batas ketat

  f(n) = Θ(g(n)) berarti f tumbuh persis seperti g, terlepas dari konstanta: f = O(g) sekaligus f = Ω(g). Notasi Ω (Omega) adalah batas bawahnya, yaitu f(n) ≥ c · g(n) untuk n yang cukup besar.

  Contoh: 3n² ≤ 3n² + 10n + 5 ≤ 4n² untuk n ≥ 11, jadi 3n² + 10n + 5 = Θ(n²).

  Dipelajari di Modul 02 · Notasi asimtotik

• P vs NPjuga: NP, NP-lengkap, NP-sulit

  Pertanyaan terbuka: apakah setiap soal yang jawabannya cepat diperiksa (NP) juga cepat diselesaikan (P)? "Cepat" berarti langkahnya paling banyak n pangkat tetap, misalnya n³. Soal NP-lengkap adalah yang tersulit di NP; belum ada yang tahu cara cepat untuk satu pun dari mereka.

  Contoh: rute terbaik mengunjungi k rumah adalah soal NP-sulit; karena itu rute_terbaik dibatasi 8 tujuan.

  Dipelajari di Modul 15 · Rakus dan backtracking

• pemecah seri

  Aturan tambahan untuk memilih satu jawaban bila beberapa jawaban sama baiknya, supaya program yang berbeda memberi hasil yang sama dan bisa diperiksa mesin.

  Contoh: tetangga dikunjungi menurut id terkecil; dua rute sama panjang dipilih yang lebih kecil secara leksikografis.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• pemrograman dinamisjuga: DP, dynamic programming

  Teknik menyelesaikan soal dengan menghitung setiap submasalah berbeda tepat sekali dan menyimpan jawabannya, lalu menyusun jawaban besar dari jawaban kecil. Cocok bila submasalah yang sama muncul berulang kali. Ditulis sebagai memo (atas ke bawah) atau tabel (bawah ke atas).

  Contoh: banyak rute di kisi 20 × 20 (lebih dari 35 miliar) dihitung dengan mengisi 400 sel.

  Dipelajari di Modul 14 · Pemrograman dinamis

• pencarian binerjuga: binary search

  Pencarian di data terurut yang setiap langkahnya memeriksa elemen tengah lalu membuang separuh calon yang pasti salah. Butuh sekitar log₂ n langkah, bukan n.

  Contoh: mencari keberangkatan pertama sesudah menit tertentu di 1.000 jadwal terurut hanya butuh 10 pembacaan.

  Dipelajari di Modul 09 · Pencarian biner dan dua penunjuk

• pencarian menyeluruhjuga: brute force

  Cara menyelesaikan soal dengan mencoba setiap kemungkinan satu per satu lalu memilih yang terbaik. Pasti benar, tetapi sering terlalu lambat karena banyaknya kemungkinan meledak.

  Contoh: mencoba semua 24 urutan empat rumah untuk mencari rute antar terpendek; 20 rumah sudah punya 2.432.902.008.176.640.000 urutan.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• penghapusan malasjuga: entri basi

  Cara "menghapus" atau memperbarui elemen di heap tanpa mencarinya: masukkan entri baru, biarkan entri lama tetap di dalam, lalu lewati entri lama (entri basi) saat ia keluar.

  Contoh: di Dijkstra, titik A masuk heap sebagai (4, A) lalu (3, A); saat (4, A) keluar belakangan, ia dilewati.

  Dipelajari di Modul 11 · Heap dan antrean prioritas

• permutations

  Fungsi modul itertools yang menghasilkan semua urutan elemen satu per satu sebagai tuple. Untuk k elemen ada k! urutan; bila masukannya terurut, urutannya keluar secara leksikografis.

  Contoh: permutations(["R11", "R16"]) menghasilkan ('R11', 'R16') lalu ('R16', 'R11').

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• pohon biner

  Pohon yang setiap simpulnya punya paling banyak dua anak, kiri dan kanan. Pohon setinggi h memuat paling banyak 2ʰ − 1 simpul.

  Contoh: heap dan pohon pencarian biner sama-sama pohon biner.

  Dipelajari di Modul 10 · Pohon dan pohon pencarian biner

• pohon pencarian binerjuga: BST

  Pohon biner yang kuncinya teratur: semua kunci di subpohon kiri sebuah simpul lebih kecil darinya, semua di kanan lebih besar. Mencari, menyisip, dan menghapus O(h), dengan h tinggi pohon.

  Contoh: mencari 7 di pohon berakar 8 turun ke 3, lalu 6, lalu ketemu 7: empat simpul.

  Dipelajari di Modul 10 · Pohon dan pohon pencarian biner

• pohon rekursi

  Gambar semua panggilan fungsi rekursif: setiap panggilan adalah satu simpul, dan panggilan yang dibuatnya menjadi anak-anaknya. Kerja total adalah jumlah kerja semua simpul; ruang yang dipakai sebanding dengan kedalamannya.

  Contoh: pohon rekursi fib(4) menghitung fib(2) dua kali dan fib(1) tiga kali.

  Dipelajari di Modul 03 · Rekursi dan induksi

• pohon rentang minimumjuga: MST, minimum spanning tree

  Himpunan sisi yang menghubungkan semua titik graf tak berarah tanpa siklus, dengan total bobot sekecil mungkin. Dicari dengan algoritma Kruskal (sisi terpendek dulu) atau Prim (menumbuhkan satu pohon).

  Contoh: kabel lampu jalan yang menyambung semua simpang dengan panjang kabel total paling kecil.

  Dipelajari di Modul 13 · Graf 2: jalur terpendek dan pohon rentang

• popleft

  Metode deque yang mengambil dan mengembalikan elemen paling depan dalam O(1). Pasangannya appendleft menambah di depan.

  Contoh: BFS memanggil antrean.popleft() untuk memproses titik yang paling lama menunggu.

  Dipelajari di Modul 05 · Stack, queue, dan deque

• quicksortjuga: pivot

  Pengurutan yang memilih satu elemen sebagai pivot, memindahkan yang lebih kecil ke kiri dan sisanya ke kanan (partisi), lalu mengurutkan kedua sisi secara rekursif. Rata-rata Θ(n log n), tetapi Θ(n²) bila pivotnya terus-menerus buruk.

  Contoh: dengan pivot 25, [29, 10, 14, 37, 13, 25] dipartisi menjadi [10, 14, 13, 25, 29, 37].

  Dipelajari di Modul 08 · Pengurutan efisien

• RecursionError

  Galat yang muncul saat rekursi melewati batas kedalaman Python, sekitar 1.000 panggilan yang belum selesai. Penyebabnya bisa kasus dasar yang terlewat, atau masukan yang memang terlalu dalam untuk rekursi.

  Dipelajari di Modul 03 · Rekursi dan induksi

• rekurensijuga: relasi rekurensi

  Persamaan yang mendefinisikan sebuah nilai dari nilai yang sama untuk masukan lebih kecil. Dipakai untuk menuliskan biaya fungsi rekursif, dan dalam pemrograman dinamis untuk menuliskan jawaban.

  Contoh: Menara Hanoi butuh M(n) = 2M(n − 1) + 1 langkah, dengan M(0) = 0; penyelesaiannya 2ⁿ − 1.

  Dipelajari di Modul 03 · Rekursi dan induksi

• rekursijuga: rekursif

  Fungsi yang memanggil dirinya sendiri untuk masukan yang lebih kecil. Rekursi yang benar punya kasus dasar dan setiap panggilannya mendekati kasus dasar itu.

  Contoh: jumlah_indeks(daftar, i) menjumlahkan daftar[i] dengan hasil jumlah_indeks(daftar, i + 1), dan berhenti saat i == len(daftar).

  Dipelajari di Modul 03 · Rekursi dan induksi

• setengah terbukajuga: rentang setengah terbuka

  Rentang [lo, hi) yang memuat lo tetapi tidak memuat hi: lo, lo + 1, ..., hi - 1. Panjangnya hi - lo dan rentangnya kosong saat lo == hi, sehingga kode batas lebih jarang meleset satu.

  Contoh: range(2, 5) dan potongan daftar[2:5] sama-sama memuat indeks 2, 3, dan 4.

  Dipelajari di Modul 09 · Pencarian biner dan dua penunjuk

• siklus

  Jalur yang kembali ke titik awalnya. Di list berantai, siklus terjadi bila sebuah simpul menunjuk balik ke simpul sebelumnya, sehingga perulangan tidak pernah bertemu None.

  Contoh: aturan dapur "A menunggu B" dan "B menunggu A" membentuk siklus, jadi tidak ada urutan kerja yang sah.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• simpuljuga: node

  Satu kotak data di struktur berantai: berisi nilai dan rujukan ke kotak lain. Di list berantai simpul menunjuk simpul berikutnya; di pohon biner, ke anak kiri dan kanan.

  Contoh: Simpul(8, kiri, kanan) adalah akar pohon pencarian biner berkunci 8.

  Dipelajari di Modul 04 · Array dinamis dan list berantai

• sorted

  Fungsi bawaan yang mengembalikan list baru berisi elemen terurut, tanpa mengubah aslinya. Ia stabil, menghitung key= sekali per elemen, dan reverse=True mengurutkan menurun.

  Contoh: sorted(pesanan, key=lambda p: p["batas_menit"]) mengurutkan pesanan menurut tenggat.

  Dipelajari di Modul 07 · Pengurutan dasar dan pembuktiannya

• spesifikasijuga: pascasyarat

  Uraian tentang apa yang harus dilakukan sebuah fungsi, tanpa menyebut caranya. Isinya dua bagian: prasyarat (yang dijamin pemanggil tentang masukan) dan pascasyarat (yang dijamin fungsi tentang keluarannya, asalkan prasyaratnya terpenuhi).

  Contoh: posisi_terkecil berprasyarat "list tidak kosong" dan berpascasyarat "mengembalikan indeks pertama nilai terkecil".

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• stabiljuga: pengurutan stabil, kestabilan

  Sifat algoritma pengurutan: elemen dengan kunci sama tetap dalam urutan aslinya. Penting saat mengurutkan bertingkat, misalnya menurut kota lalu menurut tenggat.

  Contoh: pesanan 2 dan 5 sama-sama 5.000 g; pengurutan stabil menurut berat tetap menaruh pesanan 2 di depan pesanan 5. sorted dan list.sort Python stabil.

  Dipelajari di Modul 07 · Pengurutan dasar dan pembuktiannya

• submasalah

  Versi lebih kecil dari soal yang sama, yang jawabannya dipakai untuk menyusun jawaban soal besar. Dalam pemrograman dinamis, submasalah harus didefinisikan dengan kalimat yang jelas beserta parameternya.

  Contoh: T(i, c) = nilai terbesar dari pesanan ke-i sampai akhir bila sisa kapasitas tas c gram.

  Dipelajari di Modul 14 · Pemrograman dinamis

• substruktur optimal

  Sifat soal: solusi terbaik untuk soal besar tersusun dari solusi terbaik submasalahnya. Syarat agar pemrograman dinamis dan algoritma rakus bisa benar.

  Contoh: solusi terbaik tas 4.000 g yang memuat pesanan 3 (2.000 g) berisi solusi terbaik untuk sisa 2.000 g dari pesanan sesudahnya.

  Dipelajari di Modul 14 · Pemrograman dinamis

• tabel hashjuga: hash table

  Struktur yang menyimpan pasangan kunci dan nilai di banyak ember, dengan fungsi hash yang langsung menunjuk ember tempat sebuah kunci berada. Mencari, menambah, dan menghapus rata-rata O(1). dict dan set Python adalah tabel hash.

  Contoh: indeks pesanan yang menemukan pesanan nomor 99.999 tanpa memeriksa pesanan lain.

  Dipelajari di Modul 06 · Tabel hash

• teorema master

  Jalan pintas untuk menyelesaikan rekurensi berbentuk T(n) = a · T(n/b) + Θ(nᵈ). Bandingkan a dengan bᵈ: lebih kecil berarti Θ(nᵈ), sama berarti Θ(nᵈ log n), lebih besar berarti Θ(n^(log_b a)).

  Contoh: merge sort, T(n) = 2T(n/2) + Θ(n), punya a = 2 = 2¹, jadi Θ(n log n).

  Dipelajari di Modul 03 · Rekursi dan induksi

• Terhitung

  Kelas pembungkus nilai yang menambah penghitung Terhitung.perbandingan setiap kali nilainya dibandingkan dengan <, ==, dan sebagainya. Tes K1 memakainya untuk menghitung perbandingan, termasuk di dalam max dan sorted.

  Contoh: max atas 1.000 nilai terbungkus tercatat 999 perbandingan.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• Timsort

  Algoritma pengurutan di balik sorted dan list.sort Python. Ia mencari potongan yang sudah terurut, mengurutkan potongan pendek dengan insertion sort, lalu menggabungkannya seperti merge sort. Stabil, O(n log n), dan hanya n − 1 perbandingan untuk data yang sudah terurut.

  Dipelajari di Modul 08 · Pengurutan efisien

• TopologicalSorter

  Kelas dari modul graphlib yang mencari urutan topologis. Diberi dictionary "tugas → prasyaratnya"; static_order() mengembalikan satu urutan sah, dan graf yang bersiklus memunculkan CycleError.

  Dipelajari di Modul 12 · Graf 1: menjelajah

• tumpukanjuga: stack, LIFO

  Wadah dengan aturan "terakhir masuk, pertama keluar" (LIFO): elemen masuk dan keluar dari ujung yang sama, yang disebut puncak. Di course ini operasinya masuk, keluar, dan intip.

  Contoh: tombol undo membatalkan aksi terakhir lebih dulu, jadi riwayat aksi adalah tumpukan.

  Dipelajari di Modul 05 · Stack, queue, dan deque

• tumpukan pemanggilanjuga: call stack

  Catatan Python tentang semua panggilan fungsi yang belum selesai. Setiap panggilan menempati satu bingkai berisi variabelnya; panggilan terakhir selesai lebih dulu. Python membatasi kedalamannya sekitar 1.000 bingkai.

  Contoh: saat fib(4) sedang menghitung fib(1) yang paling dalam, tumpukan berisi bingkai fib(4), fib(3), fib(2), dan fib(1).

  Dipelajari di Modul 03 · Rekursi dan induksi

• urutan topologisjuga: topological sort

  Urutan semua titik graf berarah sehingga setiap sisi u → v membuat u muncul sebelum v. Biasanya dicari dengan algoritma Kahn: kerjakan dulu yang tidak menunggu apa pun.

  Contoh: "cuci beras" sebelum "masak nasi", dan "masak nasi" sebelum "bungkus nasi".

  Dipelajari di Modul 12 · Graf 1: menjelajah

• varian

  Ukuran berupa bilangan bulat yang turun paling sedikit satu di setiap putaran perulangan (atau setiap panggilan rekursif) dan tidak bisa turun di bawah nol. Bila ada varian seperti itu, perulangannya pasti berhenti.

  Contoh: pada pencarian biner, hi - lo turun di setiap putaran, jadi perulangannya pasti selesai.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur

• yield

  Kata kunci yang menjadikan fungsi sebuah generator: alih-alih mengembalikan satu nilai, fungsi menyerahkan nilai satu per satu setiap kali for meminta, lalu melanjutkan dari tempat ia berhenti.

  Contoh: __iter__ pada list berantai menjalankan yield simpul.nilai untuk setiap simpul.

  Dipelajari di Modul 01 · Algoritma, kebenaran, dan cara mengukur