Algoritma untuk menemukan perbedaan terkecil dalam array

Kami menginginkan algoritme yang, mengingat array dengan panjang bilangan bulat, menemukan perbedaan minimum antara dua bilangan bulat dalam array. $n$

Salah satu algoritma tersebut adalah untuk mengurutkan array dan memeriksa pasangan angka yang berdekatan. Ini membutuhkan waktu . $O(n\log n)$

Apakah ada cara yang lebih cepat, misalnya algoritma ? $O(n)$

algorithms arrays dipukul
sumber

O (n)

$O(n)$ tidak lebih cepat dari

O (n \log n)

$O(n\log n)$

David Merinos

Jawaban:

Ini tergantung pada model perhitungan Anda. Jika Anda hanya membolehkan aritmatika dan perbandingan (model pohon keputusan aljabar) maka ada batas bawah untuk perbedaan elemen , masalah dalam memutuskan apakah semua elemen berbeda. Masalah Anda tentu saja lebih sulit, jadi batas bawah yang sama berlaku. $\Omega(n\log n)$

(Ada beberapa cetak halus: batas bawah hanya berlaku jika tingkat polinomial yang dibandingkan dibatasi. Jika semua yang Anda lakukan adalah membandingkan berbagai perbedaan , maka Anda baik untuk pergi. Model pohon keputusan aljabar juga memungkinkan Anda untuk membandingkan polinomial yang lebih umum dalam input, selama mereka memiliki tingkat terikat.) $x_i - x_j$

Ada model lain yang mungkin berkinerja lebih baik - misalnya, dalam beberapa model Anda dapat mengurutkan bilangan bulat dalam . Tapi saya bayangkan Anda tidak ingin mengizinkan tipuan yang digunakan dalam algoritma seperti itu. $o(n\log n)$

Yuval Filmus
sumber

Terima kasih. Apa yang Anda maksud dengan "membandingkan berbagai perbedaan "? Karena ada pasangan seperti itu, bukankah itu membutuhkan waktu ?

x_{i} - x_{j}

$x_i-x_j$

Θ (n^{2})

$\Theta(n^2)$

Ω (n^{2})

$\Omega(n^2)$

dikalahkan

Belum tentu. Algoritma berbasis perbandingan hanya diperbolehkan untuk membandingkan pasangan elemen. Di sini saya memungkinkan Anda untuk membuat pertanyaan yang lebih rumit seperti , atau bahkan . Kita tahu bahwa ada solusi yang menggunakan perbandingan dari tipe , dan perbandingan dari tipe . Pertanyaannya adalah, bisakah Anda melakukan yang lebih baik, dan jawabannya tidak, jika Anda hanya dibatasi untuk membuat kueri linear (atau, lebih umum, kueri derajat terbatas).

x_{1} - x_{2} > x_{3} - x_{4}

$x_1 - x_2 > x_3 - x_4$

x_{1} + 5 x_{8} - 17 x_{3} < - 5

$x_1 + 5x_8 - 17x_3 < -5$

O (n \log n)

$O(n\log n)$

x_{i} > x_{j}

$x_i > x_j$

O (n)

$O(n)$

x_{i} - x_{j} > x_{k} - x_{ℓ}

$x_i - x_j > x_k - x_\ell$

Yuval Filmus

Tidak yakin saya mengerti arti praktis dari keterikatan elemen ini. Tidakkah Anda memiliki O (n) yang diharapkan dengan tabel hash?

jkff

Tabel hash tidak dapat diimplementasikan menggunakan model perhitungan ini. Secara umum, batas bawah sulit dibuktikan. Model pohon keputusan aljabar adalah model di mana batas bawah non-sepele dapat dibuktikan. Saya tidak melihat bagaimana membuktikan batas bawah pada model lain - memang, batas bawah semacam itu biasanya hanya diketahui untuk fungsi acak. Anda benar bahwa mungkin ada trik algoritme yang melampaui model ini, tapi saya tidak bisa memikirkannya.

ω (n)

$\omega(n)$

o (n \log n)

$o(n\log n)$

Yuval Filmus

-1

Jika integer dalam array memiliki jumlah digit yang terbatas, Anda dapat mengurutkan array dengan algoritma sortir radix , yaitu O (kN) dan kemudian memeriksa pasangan angka yang berdekatan (O (N))? Kompleksitas yang dihasilkan adalah O ((k + 1) N), linier.

Pavel Davydov
sumber

Perhatikan kondisi di mana runtime dari jenis radix sebenarnya baik.

Raphael

@ Raphael Nah, pertanyaan awal adalah apakah algoritma linier ada, jadi saya memikirkannya. Maksud Anda k akan lebih besar dari log (N) untuk N kecil?

Pavel Davydov

k

$k$ dan adalah parameter independen, itulah sebabnya radix sort bukanlah algoritma linear-waktu untuk semua input, dan karenanya tidak bertentangan dengan sortasi terikat pada (perbandingan). (Artikel Wikipedia juga menjelaskan hal ini.)

N

$N$

Ω (n \log n)

$\Omega(n \log n)$

Raphael

@ Raphael Ya, tetapi untuk array bilangan bulat yang kurang dari 64 bit (itu adalah kasus yang cukup umum) itu akan linier. Saya akan mengedit jawaban saya. Terima kasih atas komentar anda

Pavel Davydov