2008/6/7 Hendry Luk <[EMAIL PROTECTED]>: > :-O Any algorighm yg based on array yg ngacak..... apa ini even possible > buat less than O(N)?
Tidak akan mungkin kalau tidak di-preprocess terlebih dahulu. Karena untuk ngecek-data nya saja sudah O ( N ). Preprocessnya itu digunakan untuk membuat array acak itu lebih "terstruktur". Sehingga setiap query nya bisa di jawab dengan O ( log N ). Preprocess nya itu hanya boleh 1x di awal. Dan preprocessnya itu tidak boleh lebih dari O ( N log N ) steps. Felix Halim