Versi asli cerita ini muncul di Majalah Quanta. Ilmuwan komputer sering berhadapan dengan masalah abstrak yang sulit dimengerti, tetapi algoritma baru yang menarik penting bagi siapa pun yang memiliki buku dan setidaknya satu rak. Algoritma ini mengatasi sesuatu yang disebut masalah penyortiran perpustakaan (lebih formalnya, masalah “penandaan daftar”). Tantangannya adalah merancang strategi untuk mengatur buku dalam urutan tersusun tertentu—misalnya, secara alfabetis—yang meminimalkan waktu yang dibutuhkan untuk menempatkan buku baru di rak.
Bayangkan, misalnya, bahwa Anda menyimpan buku Anda terkelompok bersama-sama, meninggalkan ruang kosong di bagian kanan rak. Lalu, jika Anda menambahkan buku karya Isabel Allende ke koleksi Anda, Anda mungkin harus memindahkan setiap buku di rak untuk memberi ruang. Itu akan menjadi operasi yang memakan waktu. Dan jika kemudian Anda mendapatkan buku karya Douglas Adams, Anda harus melakukannya lagi. Penataan yang lebih baik akan meninggalkan ruang kosong terdistribusi di seluruh rak—tetapi bagaimana, sebenarnya, seharusnya mereka didistribusikan?
Masalah ini diperkenalkan dalam sebuah makalah tahun 1981, dan ini melampaui memberikan panduan organisasi bagi para pustakawan. Itu karena masalah ini juga berlaku untuk penyusunan file di hard drive dan basis data, di mana item yang akan disusun bisa mencapai miliaran. Sistem yang tidak efisien berarti waktu menunggu yang signifikan dan biaya komputasi besar. Para peneliti telah menciptakan beberapa metode efisien untuk menyimpan item, tetapi mereka selalu ingin menentukan cara terbaik.
Tahun lalu, dalam sebuah studi yang disajikan di konferensi Foundations of Computer Science di Chicago, sebuah tim tujuh peneliti menjelaskan cara mengorganisir item yang mendekati ideal teoretis. Pendekatan baru ini menggabungkan sedikit pengetahuan tentang konten rak buku dengan kekuatan kebetulan.
“Ini adalah masalah yang sangat penting,” kata Seth Pettie, seorang ilmuwan komputer di Universitas Michigan, karena banyak struktur data yang kita andalkan saat ini menyimpan informasi secara berurutan. Dia menyebut pekerjaan baru ini “sangat terinspirasi [dan] dengan mudah salah satu makalah favorit saya tahun ini.”
Menyempitkan Batas
Jadi bagaimana cara mengukur rak buku yang tersusun dengan baik? Cara umum adalah melihat berapa lama waktu yang dibutuhkan untuk menyisipkan item individual. Tentu saja, itu bergantung pada berapa banyak item yang ada pada awalnya, nilai yang biasanya ditandai dengan n. Dalam contoh Isabel Allende, ketika semua buku harus bergerak untuk menampung satu buku baru, waktu yang dibutuhkan proporsional dengan n. Semakin besar n, semakin lama prosesnya. Ini membuat ini menjadi “batas atas” masalah: Tidak akan pernah memakan waktu lebih lama dari waktu proporsional n untuk menambahkan satu buku ke rak.
Penulis makalah tahun 1981 yang memperkenalkan masalah ini ingin tahu apakah mungkin untuk merancang algoritma dengan waktu penyetelan rata-rata jauh lebih kecil dari n. Dan memang, mereka membuktikan bahwa seseorang bisa melakukan lebih baik. Mereka menciptakan algoritma yang dijamin mencapai waktu penyetelan rata-rata proporsional dengan (log n)2. Algoritma ini memiliki dua properti: itu “deterministik,” yang berarti keputusannya tidak tergantung pada kebetulan apa pun, dan juga “halus,” yang berarti buku harus tersebar merata dalam subbagian rak di mana penyetelan (atau penghapusan) dilakukan. Penulis meninggalkan pertanyaan apakah batas atas bisa ditingkatkan lebih jauh. Selama lebih dari empat dekade, tidak ada yang berhasil melakukannya.
Namun, bertahun-tahun yang berlalu melihat peningkatan pada batas bawah. Sementara batas atas menentukan waktu maksimum yang mungkin diperlukan untuk menyisipkan buku, batas bawah memberikan waktu penyisipan yang paling cepat mungkin. Untuk menemukan solusi definitif untuk masalah, para peneliti berusaha menyempitkan celah antara batas atas dan bawah, idealnya sampai keduanya sama. Ketika itu terjadi, algoritma dianggap optimal—terikat secara tidak terelakkan dari atas dan bawah, tidak meninggalkan ruang untuk penyempurnaan lebih lanjut.