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>: > > 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