Tradeoff ruang-waktu untuk masalah elemen yang hilang

Inilah masalah yang sudah diketahui.

Diberikan array $A[1\dots n]$ dari bilangan bulat positif, menghasilkan bilangan bulat positif terkecil tidak dalam array.

Masalah dapat diselesaikan dalam $O(n)$ ruang dan waktu: membaca array, keep track di $O(n)$ ruang apakah $1,2,\dots,n+1$ terjadi, memindai untuk elemen terkecil.

Saya perhatikan Anda dapat bertukar ruang untuk waktu. Jika Anda memiliki $O(\frac{n}{k})$ hanya memori, Anda dapat melakukannya dalamputaran $k$ dan mendapatkan waktu $O(k n)$ . Dalam kasus khusus, jelas ada algoritma waktu kuadrat ruang konstan.

Pertanyaanku adalah:

Apakah ini tradeoff yang optimal, yaitu apakah $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$ ? Secara umum, bagaimana seseorang membuktikan batasan semacam itu?

Asumsikan model RAM, dengan aritmatika terbatas dan akses acak ke array di O (1).

Inspirasi untuk masalah ini: tradeoff ruang-waktu untuk palindrom dalam model satu-pita (lihat misalnya, di sini ).

complexity-theory time-complexity space-complexity sdcvvc
sumber

Tidak, Anda dapat mengurutkan array di

lalu menemukan nomor yang hilang (angka pertama harus 1, kedua harus 2, ... kalau tidak Anda akan menemukannya) di O (n), pengurutan ini dapat dilakukan dengan inplace mergesort, berarti

ruang ekstra, jadi waktu

ruang milik

. Saya tidak tahu saya mendapatkan masalah Anda dengan tepat atau tidak (karena ini saya tidak menjawabnya, Juga saya tidak tahu apakah ada ikatan yang lebih baik).

O (n \log n)

$O(n \log n)$

O (1)

$O(1)$

\cdot

$\cdot$

O (n \log n)

$O(n \log n)$

Saya menganggap input hanya baca. (Jika tidak, masalah dapat diselesaikan secara optimal dalam ruang

waktu /

: kalikan input dengan 2, dan gunakan paritas untuk mensimulasikan algoritma

)

O (n)

$O(n)$

O (1)

$O(1)$

O (n) / O (n)

$O(n)/O(n)$

sdcvvc

Apa algoritma ruang konstan? Sepertinya Anda akan memerlukan ruang

untuk versi

yang "jelas" bagi saya

\log n

$\log n$

n^{2}

$n^2$

Xodarap

Dalam model ini, bilangan bulat ukuran kata menggunakan

; jika lebih nyaman, Anda dapat menjawab varian pertanyaan apa pun dengan

O (1)

$O(1)$

untuk beberapa konstanta

time \cdot space = Ω (\frac{n^{2}}{\log^{k} n})

$\operatorname{time} \cdot \operatorname{space} = \Omega(\frac{n^2}{\log^k n})$

k

$k$

sdcvvc

@ sdcvvc, saya tidak dapat memahami algoritma

, apakah Anda akan menjelaskannya sedikit lagi? (Catat bahwa membaca bit membutuhkan

O (n) / O (1)

$O(n)/O(1)$

O (\log n)

$O(\log n)$

Jawaban:

Ini dapat dilakukan dalam operasi kata $O(n \log n)$ dan $O(1)$ kata memori (masing-masing memori $O(n \log^2 n)$ dan memori $O(\log n)$ dalam model RAM bit-level). Memang, solusinya akan didasarkan pada pengamatan berikut.

Katakanlah ada $n_0$ bahkan dan $n_1$ angka ganjil dalam rentang $[1, n + 1]$ (sehingga $n_0 \approx n_1$ dan $n_0 + n_1 = n + 1$ ). Kemudian ada $b \in \{0, 1\}$ sedemikian rupa sehingga ada paling banyak nilai $n_b - 1$ dengan paritas $b$ pada input. Memang, jika tidak ada setidaknya $n_0$ bahkan dan setidaknya $n_1$ nilai aneh di input, yang berarti bahwa setidaknya ada $n_0 + n_1 = n + 1$ nilai dalam input, kontradiksi (hanya ada $n$ dari mereka). Ini berarti bahwa kita dapat terus mencari nomor yang hilang hanya di antara angka ganjil atau genap saja. Algoritma yang sama dapat diterapkan pada bit notasi biner yang lebih tinggi juga.

Jadi algoritma kami akan terlihat seperti itu:

Misalkan kita sudah sekarang bahwa hanya ada nilai $x$ dalam input dengan modulo $2^b$ sisanya sama dengan $r \in [0, 2^b)$ tetapi ada setidaknya $x + 1$ angka dalam rentang $[1, n + 1]$ yang memiliki sisanya $r$ modulo $2^b$ (pada awalnya kita tahu pasti untuk $b = 0, r = 0$ ).
Katakanlah ada nilai $x_0$ pada input dengan sisa $r$ modulo $2^{b + 1}$ dan nilai $x_1$ pada input dengan sisa $r + 2^b$ modulo $2^{b + 1}$ (kita dapat menemukan angka-angka ini dalam sekali jalan melalui input). Jelas, $x_0 + x_1 = x$ . Selain itu, karena ada setidaknya $x + 1$ angka dalam input dengan sisa $r$ modulo $2^b$ , setidaknya satu dari pasangan $(r, b + 1), (r + 2^b, b + 1)$ memenuhi persyaratan langkah $1$ .
Kami telah menemukan angka yang hilang ketika $2^b \geqslant n + 1$ : hanya ada satu angka dalam rentang $[1, n + 1]$ yang mungkin memiliki sisa $r$ modulo $2^b$ ( $r$ sendiri jika berada dalam kisaran), jadi ada pada sebagian besar nilai nol dalam input yang memiliki sisa seperti itu. Jadi $r$ memang hilang.

Jelas, algoritme berhenti pada langkah-langkah $O(\log n)$ , masing-masing membutuhkan waktu $O(n)$ (satu kali melewati array input). Selain itu, hanya $O(1)$ kata memori yang diperlukan.

Kaban-5
sumber

Saya senang melihat pertanyaan dijawab setelah waktu itu :)

sdcvvc

Jika saya memahami definisi Anda, ini dapat dilakukan dalam waktu linier dengan ruang konstan. Ini jelas merupakan batas terendah, karena kita harus setidaknya membaca seluruh input.

Jawaban yang diberikan dalam pertanyaan ini memuaskan.

Tidak mungkin menjalankan ini dengan sedikit waktu atau ruang, dan menambahkan waktu atau ruang tambahan tidak berguna, jadi tidak ada pertukaran ruang-waktu di sini. (Amati bahwa , jadi pengorbanan yang Anda amati tidak berlaku asimptotik, dalam hal apa pun.) $n=O(n/k)$

Dalam hal pertanyaan umum Anda, saya tidak tahu teorema bagus apa pun yang akan membantu Anda membuktikan pengorbanan ruang-waktu. Pertanyaan ini tampaknya menunjukkan bahwa tidak ada jawaban yang mudah diketahui. Pada dasarnya:

Misalkan beberapa bahasa decidable di waktu (menggunakan beberapa jumlah ruang) dan ruang (menggunakan beberapa jumlah waktu). Bisakah kita menemukan sedemikian sehingga dapat ditentukan oleh yang berjalan dalam waktu dan ? $t$ $s$ $f,g$ $L$ $M$ $f(t,s)$ $g(t,s)$

tidak diketahui, dan jawaban yang kuat akan memecahkan banyak masalah terbuka (terutama tentang SC), menyiratkan bahwa tidak ada solusi yang mudah.

EDIT: Ok, dengan pengulangan (tapi aku masih mengasumsikan bahwa dengan masukan dari ukuran jumlah maksimum yang mungkin adalah ). $n$ $n+1$

Perhatikan bahwa algoritma kami harus dapat membedakan antara setidaknya jawaban yang mungkin. Misalkan pada setiap melewati data kita bisa mendapatkan paling banyak potongan data. Maka kita akan memerlukan pass untuk membedakan semua jawaban. Dengan asumsi maka kita jalankan di $n$ $k$ $n/k$ $k=n/s$ waktu. Jadi saya pikir ini membuktikan apa yang Anda inginkan. $\frac{n}{n/s}n=sn$

Kesulitannya adalah dalam menunjukkan bahwa setiap kali melalui kita hanya mendapatkan bit. Jika Anda menganggap bahwa satu-satunya operasi hukum kami adalah =, maka kami baik-baik saja. Namun, jika Anda mengizinkan operasi yang lebih rumit, maka Anda akan dapat memperoleh lebih banyak informasi. $k$

Xodarap
sumber

Pertanyaan yang Anda tautkan mengasumsikan bahwa setiap nomor muncul paling banyak satu kali. Saya tidak membuat asumsi ini, jadi solusinya tidak berlaku. Terima kasih atas tautan kedua.

sdcvvc

@ sdcvvc: Kesalahan saya, saya berasumsi Anda menggunakan versi yang saya kenal. Saya tidak memiliki jawaban yang lengkap, tetapi terlalu panjang untuk dikomentari - semoga hasil edit saya bermanfaat.

Xodarap

k

$k$

2^{k}

$2^k$

n / 2^{k}

$n/2^k$

n / k

$n/k$