Anda diberi daftar ( a, b ), dan daftar x . Hitung kapak maksimum + b untuk setiap x . Anda dapat menganggap a , b dan x adalah bilangan bulat non-negatif.
Program atau fungsi Anda harus berjalan dalam yang diharapkan (ke keacakan jika kode Anda melibatkan itu, bukan input) O ( n log n ) waktu di mana n adalah total panjang input (jumlah atau maksimum panjang dari kedua daftar).
Ini adalah kode-golf. Kode terpendek menang.
Contoh
[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]
Keluaran:
[11 12 14 16 20]
Penjelasan:
11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0
Perhatikan tentang kerumitannya:
Jika Anda menggunakan builtin yang memiliki kompleksitas kasus rata-rata yang baik, dan dapat diacak untuk mendapatkan kompleksitas yang diharapkan secara teori, Anda dapat mengasumsikan bahasa Anda melakukan itu.
Itu berarti, jika program Anda dapat diuji dalam O ( n log n ), mungkin dengan pengecualian kasus tepi karena penerapan bahasa Anda, tetapi tidak dapat dilihat secara logis dalam kode Anda sendiri, kami akan mengatakan itu adalah O ( n log n ).
sumber
O(n log(n))
? Bisakah Anda memberikan algoritma referensi?Jawaban:
Pyth -
9998 byteIni adalah terjemahan langsung dari jawaban Python @ KeithRandall. Pasti bisa bermain golf lebih banyak.
Saya akan segera memposting penjelasan.Mengambil dua daftar yang dibatasi koma, dipisahkan dengan koma melalui stdin.
Coba di sini
sumber
Python, 214 byte
Hitung cembung lambung dengan iterasi melalui input
a,b
dalama
urutan yang meningkat . Cembung lambung direkamH
menggunakan format di-1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn
manaxi
koordinat x dari persimpangana{i-1},b{i-1}
danai,bi
.Kemudian saya mengulangi input
x
dalam urutan diurutkan, memotong lambung cembung untuk mengikuti saat saya pergi.Semuanya linier kecuali untuk jenis yang O (n lgn).
Jalankan seperti:
sumber
H
linear untuk setiapx
diX
, apakah Anda tidak ?. Apakah tidak mungkin bahwa kita memiliki kompleksitas O (n ^ 2) ketika kedua daftar memiliki panjang yang sama?H
secara linear untuk masing-masingx
, tetapi karena saya melakukan inix
agar saya ingat di mana pencarian terakhir berhenti dan mulai pencarian berikutnya di sana. Jadiwhile
loop dalam dapat mengeksekusi paling banyak O (n) kali di semuax
(meskipun mungkin mengeksekusi O (n) kali untuk setiap individux
).while
loop dalam padafor
loop pertama .Haskell, 204
271byteSunting : bermain golf lebih jauh dengan memperbarui convex hull sebagai daftar (tetapi dengan kompleksitas yang sama dengan versi yang tidak diklik), menggunakan "split (x + 1)" bukannya "splitLookup x", dan menghapus semua panggilan fungsi yang memenuhi syarat seperti Predule. foldl.
Ini menciptakan fungsi f yang mengharapkan daftar (a, b) pasangan dan daftar nilai x. Saya kira itu akan terpesona oleh apa pun dalam keluarga APL menggunakan ide yang sama, tapi begini saja:
Penggunaan sampel:
Ini bekerja dalam waktu O (n log n); lihat di bawah untuk analisis.
Sunting: Ini versi yang tidak disatukan dengan analisis big-O dan deskripsi cara kerjanya:
sumber
Gangguan Umum - 648
692Dengan pencarian biner yang sebenarnya.
Penjelasan
Biarkan n menjadi panjang (a, b) dan k panjang titik.
a
(garis paralel), hanya mempertahankan garis paralel dengan maksimumb
, yang selalu lebih besar dari yang lain (kami mencegah pembagian dengan nol saat menghitung persimpangan) - O (n)diberikan daftar itu, buat lambda yang melakukan pemeriksaan interval untuk inputnya dan menghitung nilai maksimum - pohon biner dibangun di O (n) (lihat /programming//a/4309901/124319 ). Pencarian biner yang akan diterapkan memiliki O (ln (n)) kompleksitas . Dengan input contoh, kita membangun fungsi berikut (fungsi itu kemudian dikompilasi):
terapkan fungsi itu untuk semua elemen - O (k.ln (n))
Kompleksitas yang dihasilkan: O ((n + k) (ln n))) dalam skenario terburuk.
Kami tidak dapat memberikan perkiraan kompleksitas untuk jumlah total input (n + k), karena k dan n independen. Sebagai contoh, jika n secara asimtotik diabaikan, maka k , maka total kompleksitasnya adalah O (k) .
Tetapi jika kita mengira bahwa k = O (n) , maka kompleksitas yang dihasilkan adalah O (n.ln (n)) .
Contoh lainnya
Dan jika kita memindahkan kuotasi mundur untuk melihat apa yang sedang dihitung, kita dapat melihat bahwa kita bahkan tidak perlu membuat perbandingan apa pun (begitu daftar pertama diproses sebelumnya):
Ini adalah contoh lain (diambil dari komentar):
Fungsi yang efektif:
sumber
(LIST* A B C R) should be a lambda expression
.(use-package :optima)
(mengedit ...)optima
. Akhirnya, kode yang saya berikan harus dapat dievaluasi.(MAPCAR (EVAL (LAMBDA (X) ...
yang mengevaluasi jawaban. Apakah Anda meninggalkan beberapa kode debug di sana?