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
