Struktur data dengan pencarian, masukkan dan hapus dalam waktu diamortisasi

Apakah ada struktur data untuk mempertahankan daftar yang diurutkan yang mendukung operasi berikut dalam waktu diamortisasi? $O(1)$

GetElement (k) : Mengembalikan elemen ke- dari daftar. $k$
InsertAfter (x, y) : Masukkan elemen baru y ke dalam daftar segera setelah x.
Hapus (x) : Hapus x dari daftar.

Untuk dua operasi terakhir, Anda dapat mengasumsikan bahwa x diberikan sebagai pointer langsung ke struktur data; InsertElement mengembalikan pointer yang sesuai untuk y. SisipkanAfter (NULL, y) memasukkan y di awal daftar.

Misalnya, dimulai dengan struktur data kosong, operasi berikut memperbarui daftar yang dipesan seperti yang ditunjukkan di bawah ini:

InsertAfter (NULL, a) $\implies$ [Sebuah]
SisipkanSetelah (NULL, b) $\implies$ [b, a]
SisipkanSetelah (b, c) $\implies$ [b, c, a]
SisipkanSetelah (a, d) $\implies$ [b, c, a, d]
Hapus (c) $\implies$ [buruk]

Setelah lima pembaruan ini, GetElement (2) akan kembali d, dan GetElement (3) akan mengembalikan kesalahan.

Dalam Optimal Algoritma untuk Daftar Indexing dan Subset Ranking (1989) saya menemukan

solusi untuk masalah ini.

Ω (\frac{l o g n}{l o g l o g n})

$\Omega{(\frac{log\ n}{log\ log\ n})}$

PADA

@ Raphael: Saya pikir maksudnya elemen yang akan disebut

jika struktur data adalah sebuah array. Array mendukung operasi pertama dalam

waktu tetapi bukan yang kedua; daftar tertaut mendukung operasi kedua dalam

waktu tetapi bukan yang pertama.

A [k]

$A[k]$

O (1)

$O(1)$

O (1)

$O(1)$

JeffE

Juga, pohon biner seimbang mendukung kedua operasi dalam waktu

O (\log n)

$O(\log n)$

JeffE

@ Raphael: Diedit untuk memperjelas.

JeffE

@JeffE array dinamis mendukung dua yang pertama dalam

waktu diamortisasi ( cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf )

O (1)

$O(1)$

Diego

Jawaban:

TIDAK.

Fredman dan Saks membuktikan bahwa setiap struktur data yang mendukung operasi ini memerlukan setidaknya waktu diamortisasi per operasi $\Omega(\log n/\log\log n)$ . (Ini adalah referensi [1] dalam makalah oleh Dietz yang Anda sebutkan dalam komentar pertama Anda.) Batas bawah berlaku dalam model perhitungan sel probe yang sangat kuat, yang hanya mempertimbangkan jumlah alamat memori berbeda yang diakses oleh pembaruan dan kueri algoritma.

Tanpa beberapa asumsi tambahan tentang operasi pembaruan dan kueri, struktur data Dietz adalah yang terbaik (setidaknya hingga faktor konstan).

JeffE
sumber

@AT: Ikatan itu tidak pernah "terbukti salah". Ada situasi di mana itu tidak berlaku, tetapi itu adalah pernyataan yang sama sekali berbeda!

Raphael

@ AT: Pengurutan batas bawah terbukti dalam model komputasi yang jauh lebih lemah, yaitu pohon keputusan biner. Batas itu "terbukti salah" dengan mengembangkan algoritma lebih cepat yang tidak dapat digambarkan sebagai pohon keputusan biner. Untuk membuktikan kesalahan batas bawah Fredman dan Saks, Anda harus merancang algoritme yang lebih cepat yang tidak mengakses memori . Semoga berhasil.

JeffE

@ Jeff dan Raphael; tinjau jawaban saya yang lain dan konfirmasikan / tolak hasil saya ketika Anda mendapat kesempatan. Terima kasih.

PADA

$\Omega(\dfrac{\log n}{\log\log n})$

$\Omega(\log n)$

[1] Patrascu, Mihai, dan Erik D. Demaine. "Batas Bawah Logaritmik dalam Model Sel-Probe." SIAM J. Comput. 35, tidak. 4 (April 2006): 932–963. doi: 10.1137 / S0097539705447256.

DI
sumber

Ω (\log n / \log \log n)

$\Omega(\log n/\log\log n)$

Memang. Juga, dapatkah Anda mengonfirmasi bahwa batasan ini berlaku untuk masalah representasi daftar dengan kata-kata berukuran konstan?

PADA

Θ (\log n / \log \log n)

$\Theta(\log n/\log \log n)$ , dan karenanya tidak

Ω (\log n)

$\Omega(\log n)$ .

jbapple