Mempertahankan pesanan dalam daftar dalam dalam waktu

15

Masalah pemeliharaan pesanan (atau "mempertahankan pesanan dalam daftar") adalah untuk mendukung operasi:

  • singleton: membuat daftar dengan satu item, mengembalikan pointer ke sana
  • insertAfter: diberi pointer ke item, memasukkan item baru setelahnya, mengembalikan pointer ke item baru
  • delete: diberi pointer ke item, menghapusnya dari daftar
  • minPointer: diberi dua petunjuk untuk item dalam daftar yang sama, mengembalikan yang lebih dekat ke bagian depan daftar

Saya menyadari tiga solusi untuk masalah ini yang melakukan semua operasi dalam waktu diamortisasi. Mereka semua menggunakan perkalian.O(1)

Dapatkah pesanan dipertahankan dalam daftar dalam waktu diamortisasi tanpa menggunakan operasi aritmatika yang tidak ada dalam ?O(1)AC0

jbapple
sumber
Perkalian hanya baru-baru ini (sejak Pentium III) berada di . Bisakah kita memasukkan solusi yang menggunakan perkalian? AC0
AT
AC0AC0
Ditemukan di mana saya membaca tentang ini; itu tentang Pentium 4 bukan III; dan tidak mengimplementasikan multiplikasi, tetapi mengatasinya dengan instruksi baru dari prosesor itu: M. Thorup, 'On AC0 Implementasi Fusion Tree dan Atomic Heaps', dalam Prosiding Simposium Tahunan ACM-SIAM Keempat Belas pada Algoritma Diskrit, Philadelphia, PA, AS, 2003, hlm. 699–707.
AT

Jawaban: