Kalau membaca soal berikut, asumsi saya, array of integer A tersebut adalah selalu data yang baru, dan kita diminta mencari bilangan integer terkecil. Kalau permintaan nya membuat algoritma ataupun function yang selalu ready menerima data baru, mem preprocess data, lalu the next step selalu menggunakan data yang sudah di preprocess, bukankah itu sudah mem bypass satu step algoritma dari soal tersebut? CMIIW
> Diberikan array of integer A (0-based index). > Saya ingin mencari bilangan integer terkecil di array A dengan index > antara [i, j] (inclusive). > Jawabannya harus dalam O ( log N ) > > Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ). > Ada yang bisa? Regards, Hendry 2008/6/7 Felix Halim <[EMAIL PROTECTED]>: > > Saya sudah tunggu pertanyaan ini :D > > Kalau anda sort dari 0 sampai 3, maka tiap kali saya query [i, j] anda > akan melakukan sort. > Solusi anda adalah O ( N log N ) > > Itu lebih parah daripada linear scan dari i ke j, dan cari yang minimum O ( N > ). > > Yang saya mau adalah preprocess 1x, dengan complexity maximum O ( N log N ) > Lalu untuk setiap query [ i, j ] bisa di jawab hanya dengan O ( log N ). > > Felix Halim
