napa gak preprocessnya langsung swap bilangan terkecil ke paling depan? O(n), lebih efisien drpd merge sort O(n log n).
Selanjutnya... searchnya..... array[0] ;) .... O(1) Gw gak ngerti nih batasan preprocessingnya 2008/6/7 viking leon <[EMAIL PROTECTED]>: > preprocessnya pake > - merge sort = O(n log n) > > selanjutnya search bilangan pake > - binary search = O (log n) > kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time > O(1) > > --- On *Sat, 6/7/08, Hendry <[EMAIL PROTECTED]>* wrote: > > From: Hendry <[EMAIL PROTECTED]> > Subject: Re: [JUG-Indonesia] Kode menarik > To: jug-indonesia@yahoogroups.com > Date: Saturday, June 7, 2008, 12:44 PM > > soal ini kamu yang bikin? atau penjelasan berikut ini based on your > assumption? > kalau kamu yang bikin, i got no further questions, tapi kalau hanya > based on assumption, seperti nya arti dan maksud dari soal dan > penjelasan yang diberikan berikut sudah berbeda. > > Regards, > Hendry > > 2008/6/7 Felix Halim <felix.halim@ gmail.com <felix.halim%40gmail.com>>: > > > > Array A itu fixed dengan jumlah element N. > > Saya mempunyai banyak queries: > > cari bilangan terkecil antara index i dan index j (inclusive). > > > > Jadi meskipun array A itu acak, tapi array A tidak pernah berubah. > > Dan array A yang sama ini akan di query terus menerus. > > Otomatis kita harus buat query ini efisien donk? > > Nah, algo linearnya kan itu scan dari i ke j, cari yang minimum, lalu > print. > > Tapi algo itu O ( N ) jalannya. > > > > Pertanyaanya, bisakah kita "preprocess" array A ini sedemikian sehingga > > setiap query [i, j] bisa diprocess hanya dengan O ( log N ). > > > > Tetapi one-time preprocessnya tidak boleh lebih dari O ( N log N ). > > > > Felix Halim > > > >
