Algoritma waktu linier untuk menemukan shift maks

Asumsikan kita diberi larik berisi bilangan bulat tidak negatif (tidak harus berbeda). $A[1..n]$

Biarkan menjadi diurutkan dalam urutan yang tidak bertambah. Kami ingin menghitung $B$ $A$

m = max_{i \in [n]} B [i] + i .

$m = \max_{i\in [n]} B[i]+i.$

Solusi yang jelas adalah menyortir $A$ dan kemudian menghitung $m$ . Ini memberikan algoritma yang berjalan dalam waktu $O(n \lg n)$ dalam kasus terburuk.

Apakah mungkin melakukan lebih baik? Bisakah kita menghitung $m$ dalam waktu linier?

Pertanyaan utama saya adalah yang di atas. Tetapi akan menarik untuk mengetahui tentang generalisasi masalah berikut.

Biarkan $B$ menjadi $A$ diurutkan berdasarkan beberapa perbandingan oracle $\leq$ dan $f$ suatu fungsi yang diberikan oleh oracle. Diberikan $A$ dan nubuat untuk $\leq$ dan $f$ , apa yang bisa kita katakan tentang waktu yang diperlukan untuk menghitung $m = \max_{i \in [n]} f(B[i],i)$ ?

Kita masih dapat menghitung $m$ dalam waktu $O(n \lg n)$ . Tapi bisakah kita membuktikan batas bawah super-linear untuk kasus umum ini?

Jika jawabannya adalah ya, apakah batas bawahnya berlaku jika kita menganggap $\leq$ adalah urutan yang biasa pada bilangan bulat dan $f$ adalah fungsi "baik" (monoton, polinomial, linier, dll.)?

cc.complexity-theory ds.algorithms optimization sorting Kaveh
sumber

Jawaban:

Kita dapat menghitung dalam waktu linier. $m$

Untuk kesederhanaan anggap bahwa array adalah 0 berbasis: , . Kami ingin menghitung . $A[0..n-1]$ $B[0..n-1]$ $m = \max_i B[i]+i$

Biarkan . Jelas . $max = \max_i A[i]$ $max \leq m$

Biarkan menjadi setelah pengurutan. Jika kita memiliki $A[j]$ $B[k]$ $A[j] \leq max - n$

B [k] + k \leq B [k] + (n - 1) = A [j] + (n - 1) \leq (m a x - n) + (n - 1) = m a x - 1 < m a x \leq m .

$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$

Karena itu kita dapat mengabaikan ketika . Kita hanya perlu mempertimbangkan angka dalam kisaran . $A[j]$ $A[j] \leq max - n$ $[max-n, max]$

Kita dapat menggunakan jenis penghitungan untuk mengurutkan angka dalam yang berada dalam kisaran dalam waktu linier dan menggunakan daftar yang diurutkan untuk menghitung . $A$ $[max-n, max]$ $m$

Marzio De Biasi
sumber

... mmm ... tapi berapa biaya C [x] = C [x] +1?!?

Marzio De Biasi

apakah ada masalah dengan jawaban Anda? karena sepertinya baik-baik saja bagi saya: Anda mengatakan kami hanya peduli dengan elemen array dengan nilai dalam , jadi kami bisa menggunakan jenis penghitungan. Ini berfungsi untuk masalah umum setiap kali untuk semua .

[M - n, M]

$[M-n, M]$

| f (B [i], i) - B [i] | = O (n)

$|f(B[i], i) - B[i]| = O(n)$

i

$i$

Sasho Nikolov

Terima kasih @Marzio. :) Saya sedikit mengedit jawaban Anda untuk kejelasan. Jangan ragu untuk memutar kembali edit saya atau mengedit lebih lanjut.

Kaveh

Solusi ini tampaknya bekerja juga untuk semua mana untuk semua dan , .

f (x, i)

$f(x,i)$

x

$x$

i \leq n

$i\leq n$

| f (x, i) - x | = O (n)

$|f(x,i)-x| = O(n)$

Kaveh

@Kaveh: sunting tidak apa-apa! Saya menulis jawabannya dengan cepat dan saya bahkan tidak yakin dengan kebenarannya: -S

Marzio De Biasi

-1

Jika array terdiri dari bilangan bulat yang berbeda, maka , karena jarak antara entri yang berdekatan di setidaknya ; situasinya lebih menarik ketika mereka tidak perlu berbeda. $A$ $m = \max(A) + 1$ $B$ $1$

Untuk pertanyaan yang lebih umum, bayangkan situasi di mana hanya "menarik" ketika . Tampaknya mungkin untuk membangun argumen musuh yang memaksa Anda untuk meminta untuk semua yang sebelum Anda tahu , maka Anda perlu mengurutkan untuk temukan jawabannya, yang mengambil perbandingan . (Ada beberapa komplikasi karena mungkin itu kasus yang dapat kita uji apakah dalam waktu konstan daripada linear dengan menanyakan .) Ini adalah kasus bahkan jika adalah polinom (derajat tinggi). $f(B[i],j)$ $i = j$ $f(B[i],i)$ $i$ $\max_i f(B[i],i)$ $A$ $\Omega(n\log n)$ $A[i] = B[j]$ $f(A[i],j)$ $f$

Yuval Filmus
sumber

Bagaimana jika A memiliki nol - 1 nol dan satu nol? Maka jawabannya adalah n, bukan 1.

Grigory Yaroslavtsev

Hai Yuval. Ada dapat diulang angka dalam . Seperti yang dikatakan Grigory solusinya tampaknya tidak berhasil.

A

$A$

Kaveh

Saya rasa saya melihat ide Anda untuk argumen batas bawah: diberikan kita dapat menghitung dengan cepat menggunakan pasangan kueri yang dibuat untuk oleh algoritma yang menyelesaikan masalah dalam waktu . Kita dapat memastikan algoritme kueri pada semua tetapi kita tidak dapat memastikan algoritma itu tidak menanyakan pasangan lain. Namun kita dapat mengatur untuk pasangan lain menjadi nilai yang dapat dibedakan sehingga kita dapat membuang pasangan tersebut.

A

$A$

B

$B$

f

$f$

o (n \lg n)

$o(n\lg n)$

f

$f$

(B [i], i)

$(B[i],i)$

f

$f$

Kaveh