Menunjukkan bahwa interval-jumlah kueri pada array biner tidak dapat dilakukan dengan menggunakan ruang linear dan waktu konstan

Anda diberi array biner berukuran- . $n$

Saya ingin menunjukkan bahwa tidak ada algoritma yang dapat melakukan hal berikut (atau terkejut dan mengetahui bahwa algoritma tersebut ada):

1) Pra-proses array input menggunakan waktu tidak terbatas, tetapi hanya menggunakan bit . $O(n)$

2) Jawab pertanyaan dalam waktu konstan, di mana permintaan meminta jumlah bit yang diatur antara indeks dan indeks dalam array. $(x,y)$ $x$ $y$

Tampaknya waktu konstan per kueri seharusnya tidak memungkinkan algoritma membaca informasi yang cukup untuk menghitung jumlah bit yang ditetapkan.

Bagaimana kita dapat membuktikan bahwa tidak ada algoritma seperti itu?

Pertanyaan yang lebih umum adalah,

mengingat bahwa algoritma diizinkan untuk menggunakan ruang , apa batas bawah pada waktu kueri yang dapat kita peroleh? $f(n)$

Jelas, jika kita memiliki ruang kita dapat menyimpan semua jumlah parsial dan menjawab pertanyaan dalam , tetapi bagaimana jika lebih kecil? $f=\Omega(n\log n)$ $O(1)$ $f$

Anda dapat mengasumsikan bahwa ukuran kata memori adalah dan kita dapat membaca indeks dalam waktu konstan. $\Theta(\log n)$ $x,y$

ds.algorithms lower-bounds it.information-theory BPR
sumber

@ EmilJeřábek - Saya ingin algoritma menggunakan

bit (linear dalam ukuran input), bukan

kata memori. Apakah ini masuk akal?

O (n)

$O(n)$

O (n)

$O(n)$

Begitu ya, terima kasih atas klarifikasi. Sekarang, pertanyaan lain: operasi apa yang dapat Anda lakukan dalam waktu yang konstan pada kata-kata memori? Berikut ini adalah kandidat algoritma: pisahkan array dalam

-ukuran blok, dan untuk setiap blok

, simpan konten

sebagai satu kata, dan hitung bit yang diset sebelum

sebagai kata lain. Ini menghasilkan

bit. Setiap kueri dapat dijawab dengan memeriksa empat kata, dan dapat dihitung menggunakan operasi

pada kata-kata ini seperti shift, pengurangan, dan (yang paling penting) jumlah populasi. Apakah model Anda mengizinkan ini?

(\log n)

$(\log n)$

b

$b$

b

$b$

b

$b$

O (n)

$O(n)$

O (1)

$O(1)$

Emil Jeřábek

@ EmilJeřábek - Saya hanya memiliki operasi aritmatika, pengindeksan dan pencarian bit (yaitu, mencari bit tertentu dari kata) dalam pikiran. Operasi bit standar seperti shift juga dapat dipertimbangkan. Saya setuju bahwa jika kita bisa menghitung jumlah bit yang ditetapkan dalam

maka algoritma Anda memang memecahkan masalah.

O (1)

$O(1)$

Masalahnya berasal dari algoritme yang kami bangun untuk permintaan interval-jumlah atas jendela geser. Artinya, kami memiliki aliran bilangan bulat, masing-masing dalam

dan kami ingin memperkirakan jumlah interval yang diberikan. Masalah kita kemudian berkurang menjadi jumlah interval yang tepat pada array biner (jauh lebih kecil) (yang juga `` slide ''). Untuk jendela geser biner berukuran

, kami menggunakan bit

, menambahkan bit dalam waktu konstan diamortisasi dan melakukan kueri dalam

. Saya bertanya-tanya apakah permintaan waktu konstan layak, bahkan jika array tidak diperbarui.

0, 1, \dots, R

${0,1,\ldots, R}$

n

$n$

O (n)

$O(n)$

O (\log n)

$O(\log n)$

@ EmilJeřábek - terima kasih atas saran dan analisis Anda! Ini bisa menjadi jawaban untuk pertanyaan itu, meskipun itu tidak sepenuhnya menjawab kebutuhan kita. Ruang

bit merupakan kendala sulit bagi kami, dan kami ingin menunjukkan bahwa tidak ada algoritma yang dapat menjawab pertanyaan dalam waktu konstan.

O (n)

$O(n)$

Jawaban:

Saya percaya bahwa yang Anda cari adalah struktur data yang ringkas yang mendukung operasi peringkat. Lihat...

https://en.m.wikipedia.org/wiki/Succinct_data_structure

Khususnya, Anda dapat memodifikasi solusi Emils (pertama) untuk menghapus operasi penghitungan pop dan menggantinya dengan tabel pencarian (untuk detailnya lihat artikel wiki). Dengan mengurangi ukuran blok menjadi (log n) / 2 bit, tabel pencarian menggunakan o (n) bit.

Benjamin Sach
sumber

(* facepalm *) Tabel pencarian, jelas. Kenapa aku tidak memikirkan itu.

Emil Jeřábek

Mengingat komentar OP di atas, perlu dicatat bahwa struktur dapat dengan mudah diimplementasikan sebagai jendela geser sehingga memindahkan jendela dengan satu bit (atau bahkan blok) juga membutuhkan waktu yang konstan.

Emil Jeřábek

@ EmilJeřábek - menerjemahkan solusi Anda ke pengaturan jendela geser tidak lurus ke depan. Alih-alih menghitung jumlah bit set di seluruh array-bagian yang mendahului blok saat ini, kita perlu menghitung jumlah bit set dalam jendela geser yang mendahului blok ini, yang tampaknya tidak bisa dilakukan dalam waktu konstan. Apakah saya kehilangan sesuatu?

Tidak, kamu tidak perlu melakukan itu. Karena Anda pada akhirnya akan mengurangi jumlah untuk

dari jumlah untuk

, tidak masalah jika semua jumlah yang disimpan dimatikan dengan jumlah yang tetap; dengan kata lain, tepi kiri jendela geser dapat diberi jumlah yang sewenang-wenang. Dengan demikian, saat memindahkan jendela, Anda hanya perlu memperbarui hitungan untuk blok tempat elemen baru berada. Dari waktu ke waktu, Anda perlu mengurangi semua penghitungan agar tidak menempati terlalu banyak ruang, tetapi pekerjaan kecil ini dapat dengan mudah didistribusikan sehingga hanya membutuhkan O (1) waktu untuk setiap kueri yang diberikan.

x

$x$

y

$y$

Emil Jeřábek

Sebenarnya, gangguan pada kalimat terakhir dapat dihindari secara elegan dengan menghitung semua jumlah modulo angka tetap lebih besar dari

n

$n$

Emil Jeřábek

Saya tidak akan begitu yakin algoritma seperti itu tidak ada; pasti ada algoritma yang sangat dekat. Di bawah ini, adalah , adalah , adalah logaritma iterated , dan adalah $\log n$ $\log_2n$ $\log^{(k)}n$ $\mathop{\underbrace{\log\dots\log}_{k\text{ times}}}n$ $\log^*n$ $\tilde O(t(n))$ . $O(t(n)\operatorname{polylog}(t(n)))$

Proposisi: Ada algoritma yang mencapai

ruang dan permintaan waktu untuk konstanta ; $O(n\log^{(k)}n)$ $O(1)$ $k$

spasi dan waktu kueri . $O(n)$ $\tilde O(\log^*n)$

Algoritma bekerja sebagai berikut. Ada parameter dan tergantung pada . Kami membagi ukuran input- array menjadi ukuran- blok (level 1); kami membagi setiap blok level-1 menjadi ukuran blok (level 2); dan seterusnya hingga level . (Mari kita berpura-pura semua adalah kekuatan dari , masalah menghindari dengan keterbagian.) Lalu: $k>0$ $n=b_0>b_1>\dots>b_k>0$ $n$ $b_0$ $b_1$ $b_2$ $k$ $b_i$ $2$

Untuk setiap dan setiap blok level- , kami menyimpan jumlah bit yang ditetapkan dalam interval dari awal blok ke batas level blok- . $i=1,\dots,k$ $i$ $(i-1)$
Untuk menyelesaikan query, kita menjumlahkan nomor disimpan sesuai dengan indeks, dan menghitung set bit sebelum indeks di tingkat-nya blok. Kami melakukan semua ini untuk dan secara terpisah, dan kurangi hasilnya. $k$ $k$ $x$ $y$

(Jika parameter tidak mudah dihitung, kami mungkin juga menyimpannya.) $b_i$

Ini ruang menggunakan pengaturan dan kueri waktu

n \sum_{i = 1}^{k} \frac{\log b_{i - 1}}{b_{i}},

$n\sum_{i=1}^k\frac{\log b_{i-1}}{b_i},$

O (k + b_{k}) .

$O(k+b_k).$

Dalam proposisi, untuk 1., kita membiarkan menjadi konstan, dan menempatkan untuk , . $k$ $b_i=\log^{(i)}n$ $0<i<k$ $b_k=1$

$k=\log^*n$

b_{i} = i (\log i)^{3} \log^{(i)} n .

$b_i=i(\log i)^3\log^{(i)}n.$

n \sum_{i = 1}^{k} \frac{\log^{(i)} n + 2 \log i}{i (\log i)^{3} \log^{(i)} n} \leq n \sum_{i = 1}^{\infty} \frac{3}{i (\log i)^{2}} = c n

$n\sum_{i=1}^k\frac{\log^{(i)}n+2\log i}{i(\log i)^3\log^{(i)}n}\le n\sum_{i=1}^\infty\frac{3}{i(\log i)^2}=cn$

c

$c$

Emil Jeřábek
sumber

$O(n)$ $n\cdot(1+o(1))$

$n$ $\{1,2,\ldots,n\}$ $i'th$ $i$

BPR
sumber