Batas Bawah untuk Struktur Data

14

Apakah hasil diketahui yang mengesampingkan keberadaan struktur data "terlalu-baik-untuk-menjadi-benar"?

Misalnya: dapatkah seseorang menambahkan fungsi dan ke dalam struktur data pemeliharaan pesanan (lihat Dietz dan Sleator STOC '87 ) dan masih mendapatkan operasi waktu ? $Split$ $Join$ $\mathcal{O}(1)$

Atau: dapatkah seseorang mengimplementasikan set yang diperintahkan dengan kunci integer dan operasi waktu ? Tentu saja ini setidaknya sama sulitnya dengan menemukan algoritma waktu linear untuk menyortir bilangan bulat. $\mathcal{O}(1)$

Apakah jawabannya terbukti tidak untuk salah satu dari pertanyaan ini? Apakah hasil batas bawah dikenal untuk struktur data alami?

ds.data-structures big-list lower-bounds time-complexity Shaun Harker
sumber

Berbagai hal berubah jika kita dapat menambahkan batasan pada ruang masalah. Sebagai contoh, jika kita memiliki seperangkat kunci yang terbatas dan memori yang cukup, kita dapat mengurutkannya dalam waktu linier menggunakan vektor bit.

jetru

1

Saya pikir alasan Anda tidak mendapatkan terlalu banyak jawaban untuk pertanyaan ini adalah karena ada begitu banyak kemungkinan. Banyak, banyak struktur data yang mengenal batas bawah, dan sulit untuk tidak hanya tersandung. Pencarian Google untuk "struktur data" "batas bawah" mencakup, bagi saya, 5 makalah yang belum disebutkan di utas ini. Saya pikir Anda akan lebih berhasil menjawab pertanyaan Anda jika Anda membatasinya, mungkin dengan menghapus bagian tentang "struktur data alami [s]" dan hanya bertanya tentang pemeliharaan daftar atau kumpulan bilangan bulat yang dipesan (tetapi tidak keduanya dalam satu pertanyaan).

jbapple

Saya menghilangkan bahwa 5 makalah yang saya temukan dalam pencarian Google berada pada halaman pertama dari hasil pencarian.

jbapple

@ jbapple: Anda benar! Saya pikir klik dari orang-orang di komunitas ini yang mencoba membantu saya dengan pertanyaan saya telah mendorong hasil yang baik ke daftar teratas. (Misalnya, halaman INI sekarang ada dalam daftar!) Saya tidak ingat itu berguna ketika saya pertama kali melakukan pencarian, atau saya kemungkinan akan membatasi pertanyaan seperti yang Anda sarankan. (Atau saya adalah boneka besar, itu mungkin juga. :))

Shaun Harker

19

Ada pembicaraan yang sangat bagus tentang batas bawah dinamis pada grafik oleh Mihai Pătraşcu. Singkatnya (pada hal.20 dari slide), kami memiliki batas yang lebih rendah dalam hal waktu permintaan $t_q$ dan memperbarui waktu (insert tepi): $t_u$

masukkan deskripsi gambar di sini

Lihat kertas untuk detailnya. Beberapa makalah lain dari Mihai juga relevan dan bagus.

UPDATE: Saya menemukan bahwa tesis PhD-nya " Teknik Batas Bawah untuk Struktur Data " memberikan batas bawah untuk banyak masalah struktur data pusat menggunakan teknik yang dikembangkannya. Ini tentu layak dibaca.

Hsien-Chih Chang 張顯之
sumber

1

Tesis itu luar biasa, terima kasih banyak untuk membagikan tautannya.

Shaun Harker

6

Jawaban untuk semua pertanyaan Anda tergantung pada model perhitungan. Misalnya, pada banyak mesin, mengalikan bilangan bulat lebih mahal daripada menambahkannya. Beberapa model mencerminkan ini, sementara beberapa tidak.

$O(\sqrt{\log n/ \log \log n})$

jbapple
sumber

Bagus. Tapi sepertinya Anda melebih-lebihkan hasilnya di koran Andersson dan Thorup. Ini hanya berlaku untuk struktur ruang linear, tidak semua struktur ruang polinomial.

Shaun Harker

2

Andersson dan Thorup mengutip Beame dan Fich untuk ruang polinomial: "Batas bawah mengikuti dari hasil Beame dan Fich. Ini menunjukkan bahwa bahkan jika kita hanya ingin mendukung operasi penyisipan dan pendahulunya dalam ruang polinomial, salah satu dari dua operasi ini memiliki batas kasus terburuk Ω (sqrt (log n / log log n)), cocok dengan batas atas umum kami. Kami mencatat bahwa seseorang dapat menemukan batas dan pertukaran yang lebih baik untuk beberapa operasi individu. Memang, kami akan mendukung min, operasi maks, pendahulu, penerus, dan hapus dalam waktu yang konstan, dan hanya lakukan penyisipan dan pencarian dalam waktu Θ (sqrt (log n / log log n)). "

jbapple

Saya melihat, ruang linear masuk untuk mengiklankan batas atas , tetapi Corollary 3.10 dari Beame dan Fich memberikan ruang-poli batas bawah , seperti yang Anda katakan dan saya dengan bodohnya bertentangan. Itu juga terjadi pada saya bahwa seseorang mungkin ingin mengiklankan waktu terburuk untuk batas atas sementara iklan diamortisasi untuk batas bawah. Makalah Andersson dan Thorup mengutip (halaman 5) Beame dan Fich untuk batas bawah yang diamortisasi (dan atas). Tapi sepertinya akibat wajar hanya memberikan batas bawah untuk kasus terburuk. Mungkin seseorang bisa memberi saya petunjuk tentang itu juga?

Shaun Harker

2

$O(n \log n)$ untuk membuktikan tidak adanya superstruktur.

Selain itu, tidak jarang menggunakan argumen teori informasi (misalnya kompleksitas Kolmogorov) untuk membuktikan batas yang lebih rendah untuk struktur data.

chazisop
sumber

Batas Bawah untuk Struktur Data

Jawaban: