Masalah pemeliharaan pesanan (atau "mempertahankan pesanan dalam daftar") adalah untuk mendukung operasi:
singleton
: membuat daftar dengan satu item, mengembalikan pointer ke sanainsertAfter
: diberi pointer ke item, memasukkan item baru setelahnya, mengembalikan pointer ke item barudelete
: diberi pointer ke item, menghapusnya dari daftarminPointer
: 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.
- Athanasios K. Tsakalidis: Mempertahankan urutan dalam daftar tertaut yang digeneralisasi
- Dietz, P., D. Sleator, Dua algoritma untuk menjaga ketertiban dalam daftar
- Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, dan Jack Zito, "Dua Algoritma Sederhana untuk Mempertahankan Ketertiban dalam Daftar"
Dapatkah pesanan dipertahankan dalam daftar dalam waktu diamortisasi tanpa menggunakan operasi aritmatika yang tidak ada dalam ?
ds.data-structures
soft-question
pl.programming-languages
graph-theory
tree
cc.complexity-theory
pcp
co.combinatorics
cg.comp-geom
pr.probability
vc-dimension
cc.complexity-theory
complexity-classes
relativization
soft-question
advice-request
career
soft-question
research-practice
paper-review
journals
co.combinatorics
cc.complexity-theory
complexity-classes
pr.probability
average-case-complexity
cc.complexity-theory
lo.logic
descriptive-complexity
finite-model-theory
ds.algorithms
cc.complexity-theory
approximation-hardness
csp
pcp
cc.complexity-theory
circuit-complexity
jbapple
sumber
sumber
Jawaban:
Iya!
Lihat juga latihan 8.12 dari struktur data terbuka dan "Metode baru untuk menyeimbangkan pohon pencarian biner" Roura .
sumber