Masalah umum 3SUM (k-SUM)?

29

Masalah 3SUM mencoba mengidentifikasi 3 bilangan bulat dari himpunan dengan ukuran sehingga .S n a + b + c = 0Sebuah,b,cSnSebuah+b+c=0

Diduga bahwa tidak ada solusi yang lebih baik daripada kuadratik, yaitu . Atau dengan kata lain: .o ( n log ( n ) + n 2 )Hai(n2)Hai(nlog(n)+n2)

Jadi saya bertanya-tanya apakah ini akan berlaku untuk masalah umum: Cari integer untuk dalam himpunan ukuran sehingga . i [ 1 .. k ] S n i [ 1 .. k ] a i = 0Sebuahsayasaya[1 ..k]Snsaya[1 ..k]Sebuahsaya=0

Saya pikir Anda dapat melakukan ini di untuk k \ geq 2 (mudah untuk menggeneralisasi algoritma k = 3 sederhana). Tetapi apakah ada algoritma yang lebih baik untuk nilai k lainnya ?k 2 k = 3 kHai(nlog(n)+nk-1)k2k=3
k

bitmask
sumber
berita terbaru / makalah tentang 3SUM yang melihat batas bawah pada kompleksitas pohon keputusannya
vzn

Jawaban:

27

k -SUM dapat diselesaikan lebih cepat sebagai berikut.

  • Untuk genap k : Hitung daftar S diurutkan dari semua jumlah elemen input k/2 . Periksa apakah S mengandung angka x dan negasi -x . Algoritma berjalan dalam waktu O(nk/2logn) .

  • Untuk odd k : Hitung daftar S diurutkan dari semua jumlah elemen input (k1)/2 . Untuk setiap elemen input a , periksa apakah S berisi x dan ax , untuk beberapa angka x . (Langkah kedua pada dasarnya adalah algoritma waktu O(n2) untuk 3SUM.) Algoritma ini berjalan dalam waktu O(n(k+1)/2) .

Kedua algoritma adalah optimal (kecuali mungkin untuk faktor log ketika k adalah lebih besar dan lebih besar dari 2 ) untuk setiap konstanta k dalam batasan tertentu yang lemah tapi alami dari model pohon keputusan linear perhitungan. Untuk detail lebih lanjut, lihat:

JeffE
sumber
stackoverflow.com/a/14737071/511736 menyarankan algoritma O (n ^ 2) ketika k = 4
Kowser
1
Hashing curang. Algoritma yang dijelaskan di StackOverflow hanya berjalan dalam waktu O (n ^ 2) untuk input integer, dan hanya dengan probabilitas tinggi, dan hanya jika Anda menggunakan fungsi hash acak yang sesuai. Algoritme dalam jawaban saya berfungsi dalam model RAM nyata, semuanya sepenuhnya deterministik, dan batas waktu adalah yang terburuk. Anda juga dapat mengurangi faktor log dalam pengaturan bilangan bulat menggunakan "trik bit", tapi itu agak membosankan.
JeffE
12

n Ω ( d ) 2 o ( n )d -SUM membutuhkan waktu kecuali k-SAT dapat diselesaikan dalam waktu untuk konstanta k. Ini ditunjukkan dalam sebuah makalah oleh Mihai Patrascu dan Ryan Williams (1).nΩ(d)2o(n)

Dengan kata lain, dengan asumsi hipotesis waktu eksponensial , algoritma Anda optimal hingga faktor konstan dalam eksponen (faktor polinomial dalam )n

(1) Mihai Patrascu dan Ryan Williams. Tentang Kemungkinan Algoritma SAT Lebih Cepat. Proc Simposium ACM / SIAM ke 21 tentang Algoritma Diskrit (SODA2010)

SamM
sumber
3

Berikut adalah beberapa pengamatan sederhana.

Untuk , Anda dapat melakukannya dalam waktu dengan memindai array untuk nol. Untuk , Anda dapat melakukannya tanpa hashing dalam waktu . Sortir array lalu pindai. Untuk setiap elemen melakukan pencarian biner untuk . Ini menghasilkan kompleksitas total . Untuk kasus Anda dapat melakukannya dalam waktu dengan mengakumulasi array dan memeriksa hasilnya.Θ ( n ) k = 2 Θ ( n log n ) i - i Θ ( n log n ) k = n Θ ( n )k=1Θ(n)k=2Θ(nlogn)saya-sayaΘ(nlogn)k=nΘ(n)

Untuk beberapa referensi lainnya, lihat halaman Proyek Masalah Terbuka untuk 3SUM .

Juho
sumber
-1

Lihat http://arxiv.org/abs/1407.4640

Algoritma baru untuk memecahkan masalah rSUM Valerii Sopin

Abstrak:

Algoritme yang ditentukan disajikan untuk menyelesaikan masalah rSUM untuk setiap r alami dengan penilaian sub-kuadrat kompleksitas waktu dalam beberapa kasus. Dalam hal jumlah memori yang digunakan, algoritma yang diperoleh juga memiliki urutan sub-kuadrat. Gagasan algoritma yang diperoleh didasarkan tidak mempertimbangkan angka integer, melainkan k∈N bit berturut-turut dari angka-angka ini dalam sistem numerasi biner. Terlihat bahwa jika jumlah bilangan bulat sama dengan nol, maka jumlah bilangan yang disajikan oleh k bit berturut-turut dari angka-angka ini harus cukup "dekat" dengan nol. Ini memungkinkan untuk membuang angka-angka, yang fortiori, tidak menentukan solusinya.

Ini adalah sesuatu yang baru dalam masalah ini.

pengguna20970
sumber
1
Bisakah Anda mengutip secara eksplisit hasil dari artikel yang relevan dengan pertanyaan? (Menempelkan abstraksi mungkin ok, jika artikel itu relevan secara keseluruhan.) Posting di SE seharusnya lebih dari sekadar tautan.
FrankW
1
Sebagaimana adanya, jawaban ini adalah komentar (berpotensi bermanfaat), bukan jawaban. Karena itu harus mengandung beberapa konten asli, misalnya Anda menggambarkan algoritma dengan kata-kata Anda sendiri. Apakah kamu mau melakukan itu? Saya dapat mengonversi jawaban Anda menjadi komentar jika tidak. (Saya sadar Anda tidak dapat berkomentar karena perwakilan Anda.)
Raphael
Itu tidak terlihat seperti kertas yang kredibel. Klaim "kompleksitas waktu sub-kuadrat dalam beberapa kasus" bukanlah pernyataan yang berguna. Kompleksitas waktu adalah definisi waktu berjalan terburuk. Bubble sort berjalan dalam waktu linier dalam beberapa kasus, tetapi kompleksitas waktunya tetap kuadratik.
DW