Algoritme waktu linear deterministik untuk memeriksa apakah satu array merupakan versi yang diurutkan dari yang lain

Pertimbangkan masalah berikut:

Input: dua array $A$ dan $B$ dengan panjang $n$ , di mana $B$ berada dalam urutan urutan.

Pertanyaan: apakah $A$ dan $B$ berisi item yang sama (dengan multiplisitasnya)?

Apa algoritma deterministik tercepat untuk masalah ini?
Apakah bisa diselesaikan lebih cepat daripada menyortirnya? Bisakah masalah ini diselesaikan dalam waktu linier deterministik?

algorithms reference-request sorting Albert Hendriks
sumber

FWIW pendekatan probabilistik hashing dengan fungsi hash independen-order. Carter dan Wegman menulis salah satu makalah asli tentang ini ( sciencedirect.com/science/article/pii/0022000081900337 ), tapi saya belum melihat apa pun dalam kutipan makalah yang menunjukkan algoritma deterministik (sejauh ini).

KWillets

Pernyataan yang Anda kutip adalah tentang model mesin Turing, yang hanya menarik secara teoritis. Algoritma biasanya dianalisis sehubungan dengan model RAM.

Yuval Filmus

ah, maka itulah model yang saya cari. Saya menyesuaikan pertanyaan.

Albert Hendriks

Mengapa Anda tidak menjumlahkan item dalam array dan kemudian membandingkan penjumlahan? Mengenai judul Anda, ini linear dan menjawab pertanyaan 'apakah satu array merupakan versi yang diurutkan dari yang lain? ' Saya sadar bahwa itu bukan model mesin Turing, tetapi solusi praktis.

atayenel

@AlbertHendriks Anda (kemungkinan besar) tidak dapat mengurutkan array di

O (n \log n)

$O(n\log n)$ pada mesin Turing. Beberapa batas bawah pada SAT (misalnya cs.cmu.edu/ ~ryanw/automated-lbs.pdf ) sebenarnya untuk mesin RAM, maaf untuk komentar saya sebelumnya yang menyesatkan.

Yuval Filmus

Jawaban:

Anda belum menentukan model perhitungan Anda, jadi saya akan menganggap model perbandingan.

Pertimbangkan kasus khusus di mana array diambil dari daftar Dengan kata lain, elemen ke- adalah atau . $B$

{1, 2} \times {3, 4} \times \dots \times {2 n - 1, 2 n} .

$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$

i

$i$

2 i - 1

$2i-1$

2 i

$2i$

Saya mengklaim bahwa jika algoritma menyimpulkan bahwa dan mengandung unsur-unsur yang sama, bahwa algoritma telah dibandingkan setiap elemen dalam untuk rekan di . Memang, anggaplah bahwa algoritma menyimpulkan bahwa dan mengandung unsur-unsur yang sama, tetapi tidak pernah membandingkan elemen pertama dari dengan mitranya di . Jika kita mengganti elemen pertama maka algoritme akan berjalan dengan cara yang persis sama, meskipun jawabannya berbeda. Ini menunjukkan bahwa algoritma harus membandingkan elemen pertama (dan unsur lainnya) dengan mitranya di . $A$ $B$ $B$ $A$ $A$ $B$ $B$ $A$ $A$

Ini berarti bahwa jika dan mengandung elemen yang sama, maka setelah memverifikasi ini algoritma mengetahui urutan diurutkan . Karena itu ia harus memiliki setidaknya daun berbeda, dan karena itu butuh waktu . $A$ $B$ $A$ $n!$ $\Omega(n\log n)$

Yuval Filmus
sumber

Saya akan berpikir ini akan menyiratkan bahwa

secara umum, tetapi ternyata model perbandingannya berbeda dengan itu.

P = Ω (n \log n)

$P = \Omega(n\log n)$

Albert Hendriks

@AlbertHendriks, ini adalah model yang sama yang digunakan untuk menunjukkan n lg dan batas bawah untuk penyortiran. Ini berarti bahwa satu-satunya operasi yang dapat Anda lakukan adalah perbandingan maka Anda tidak dapat melakukan lebih baik. Saya pikir ini menjawab pertanyaan Anda.

Kaveh

[Cntd] kami tidak memiliki batas yang lebih kuat bahkan untuk menyortir! dan jika Anda dapat mengurutkan lebih cepat dari n lg n maka Anda dapat menggunakannya untuk menyelesaikan masalah lebih cepat dari n lg n.

Kaveh

@AlbertHendriks, apakah Anda tahu tentang algoritma waktu linear untuk menyortir bilangan bulat? Cari di CLRS. Kasing Anda mungkin salah satu kasing di mana kami dapat mengurutkan dalam waktu linier.

Kaveh

Integer dapat disortir dalam

(lihat nada.kth.se/~snilsson/fast-sorting ), atau dalam waktu yang diharapkan

O (n \log \log n)

$O(n\log\log n)$

(lihatieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1181890), atau bahkan dalam waktu linier jika ukuran kata cukup besar (lihat LNCS 8503, hlm. 26ff).

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

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

Yuval Filmus

$O(\log n)$ $O(1)$ $n^{O(1)}$

$a_1,\ldots,a_n$ $b_1,\ldots,b_n$ $1/n$

\prod_{i = 1}^{n} (x - a_{i}) = \prod_{i = 1}^{n} (x - b_{i}) .

$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$

p

$p$

x_{0}

$x_0$

\prod_{i = 1}^{n} (x_{0} - a_{i}) \equiv \prod_{i = 1}^{n} (x_{0} - b_{i}) (\mod p) .

$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$ Jika array sama, tes akan selalu berlalu, jadi mari kita berkonsentrasi pada kasus di mana array berbeda. Secara khusus, beberapa koefisien adalah tidak nol. Karena memiliki magnitudo , koefisien ini memiliki magnitudo , dan memiliki paling banyak prime faktor ukuran . Ini berarti bahwa jika kita memilih set setidaknya bilangan prima ukuran setidaknya (katakanlah), maka untuk prime acak dari set ini akan berlaku dengan probabilitas setidaknya yang

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i})

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$

a_{i}, b_{i}

$a_i,b_i$

n^{O (1)}

$n^{O(1)}$

2^{n} n^{O (n)} = n^{O (n)}

$2^n n^{O(n)} = n^{O(n)}$

O (n)

$O(n)$

Ω (n)

$\Omega(n)$

n^{2}

$n^2$

p

$p$

n^{2}

$n^2$

p

$p$

1 - 1 / n

$1-1/n$

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i}) ≢ 0 (\mod p) .

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$ Modulo acak akan menyaksikan ini dengan probabilitas (karena polinomial derajat paling banyak memiliki paling banyak akar).

x_{0}

$x_0$

p

$p$

1 - n / p \geq 1 - 1 / n

$1-n/p \geq 1-1/n$

n

$n$

n

$n$

Kesimpulannya, jika kita memilih ukuran acak kira-kira antara sekumpulan setidaknya bilangan prima yang berbeda, dan modulo acak , maka ketika array tidak mengandung elemen yang sama, pengujian kami akan gagal dengan probabilitas . Menjalankan tes membutuhkan waktu karena cocok dengan jumlah kata mesin yang konstan. $p$ $n^2$ $n^2$ $x_0$ $p$ $1-O(1/n)$ $O(n)$ $p$

Menggunakan pengujian waktu polinomial waktu dan karena densitas bilangan prima ukuran kira-kira adalah , kita dapat memilih prime waktu secara acak . Memilih acak modulo dapat diimplementasikan dalam berbagai cara, dan dibuat lebih mudah karena dalam kasus kami, kami tidak perlu acak-benar seragam . $n^2$ $\Omega(1/\log n)$ $p$ $(\log n)^{O(1)}$ $x_0$ $p$ $x_0$

Kesimpulannya, algoritma kami berjalan dalam waktu , selalu menampilkan YA jika array berisi elemen yang sama, dan menghasilkan TIDAK dengan probabilitas jika array tidak mengandung elemen yang sama. Kita dapat meningkatkan probabilitas kesalahan untuk untuk setiap konstan . $O(n)$ $1-O(1/n)$ $1-O(1/n^C)$ $C$

Yuval Filmus
sumber

Meskipun algoritma ini diacak, itu menjelaskan bagaimana menerapkan ide-ide dalam beberapa jawaban lain sehingga mereka benar-benar berfungsi. Ini juga memiliki keunggulan dibandingkan pendekatan hashtable: itu ada di tempat.

Yuval Filmus

Saya pikir OP tidak suka algoritma probabilistik karena dia tidak suka algoritma waktu linier yang diharapkan menggunakan tabel hash.

Kaveh

Kaveh kamu benar. Tetapi tentu saja solusi ini juga menarik dan harus dijaga, itu memecahkan kasus untuk algoritma probabilistik. Juga, saya pikir itu menggunakan model yang saya cari.

Albert Hendriks

Saya hanya ingin tahu apakah notasi O (1 / n) sudah benar. Tentu saja saya tahu apa yang Anda maksud, tapi saya pikir dengan definisi big-O ini setara dengan O (1).

Albert Hendriks

Tidak semuanya. Kuantitas yang dibatasi oleh cukup besar untuk . Itu jaminan yang lebih baik daripada .

C / n

$C/n$

n

$n$

O (1)

$O(1)$

Yuval Filmus

-3

saya akan mengusulkan algoritma lain (atau setidaknya skema algoritma seperti itu)

Skema ini mengasumsikan nilai-nilai (diasumsikan " bilangan bulat ") berada dalam kisaran (sempit?) Antara $[min,max]$

Dalam waktu memindai dua array, kita dapat menemukan dan nilai untuk keduanya dan multiplisitasnya, jika ini berbeda, array tidak permutasi satu sama lain $O(n)$ minmax
Kurangi mindari semua nilai dari kedua array (di sini fakta bahwa satu array sudah dalam urutan diurutkan tidak diperhitungkan, mungkin ini dapat ditingkatkan)
Asumsikan nilai dalam array mewakili massa dan kami menerapkan akselerasi / kecepatan untuk masing-masing besarnya (ini dapat ditingkatkan ke besarnya dalam kasus-kasus tertentu) $1$ $c > 1$
gerakkan massa hingga mencapai nilai maksimum max-min, ini memiliki kompleksitas . Hal ini memungkinkan untuk menemukan nilai yang sama dan multiplisitasnya, jika berbeda, array tidak permutasi satu sama lain. Lain memutuskan array adalah permutasi satu sama lain. $O((max-min)n)$

perhatikan skema algoritma di atas dapat (deterministik) cukup cepat dalam banyak situasi praktis.

Skema algoritma di atas adalah variasi pada algoritma pengurutan linear-waktu menggunakan " massa bergerak ". Intuisi fisik di balik algoritma pengurutan " massa bergerak " adalah sebagai berikut:

Asumsikan nilai setiap item sebenarnya mewakili besarnya massa dan bayangkan mengatur semua item dalam garis dan menerapkan gaya akselerasi yang sama.

Kemudian setiap item akan bergerak ke jarak yang terkait dengan massanya, jarak lebih besar lebih kecil dan sebaliknya. Kemudian untuk mengambil item yang diurutkan cukup mengumpulkan item dalam urutan terbalik berdasarkan jarak yang ditempuh.

Algoritma ini linear-waktu dan deterministik , tetapi ada peringatan bahwa jumlah gaya akselerasi awal dan jarak untuk melakukan perjalanan (atau waktu untuk menunggu) terkait dengan distribusi nilai (yaitu " massa ", faktor di atas). Satu juga dapat mencoba untuk mendiskritasikan ruang untuk item untuk melakukan perjalanan ke kotak dan mendapatkan faktor konstan dalam kecepatan algoritma (dan menggunakan rutin penyortiran cepat untuk mengurutkan item yang berbeda dalam sel yang sama ). $max-min$

Dalam hal ini, algoritma di atas mirip dengan algoritma pengurutan berbasis numerik (mis. Radix-sort , menghitung-sort )

Orang mungkin berpikir bahwa algoritma ini mungkin tidak berarti banyak, tetapi itu menunjukkan setidaknya satu hal. Bahwa, " mendasar ", pada tingkat fisik, menyortir angka acak adalah operasi linier dalam jumlah item.

Nikos M.
sumber

Dalam hal mengumpulkan barang-barang dalam urutan terbalik jarak yang ditempuh, bukankah itu berarti perbandingan di tingkat implementasi, dan pada titik itu Anda tidak perlu menyortir "jarak"?

JustAnotherSoul