Pake RMQ yang O(log N) bisa dapet segini : Preprocess Time: 0.372 1000000 Queries Time: 0.372 TOTAL Time: 0.744
Pake RMQ yang O(1) dapet nya segituan juga. [Spoiler] http://andrian.kurniady.net/Minimum.java [/Spoiler] Bener gak? :-D -Andrian Kurniady 2008/6/10 Felix Halim <[EMAIL PROTECTED]>: > Berikut code BST yang run hanya dalam O ( log N ). > Dengan pre-processing time O ( N ). > > Bayangkan anda adalah Google. > Yang mempunyai 1 juta data dalam suatu array. > Karena pengguna google itu banyak, maka yang query data ke Google akan > sangat banyak. > Masing2 query itu ingin mengetahui value terkecil dari index i sampai j. > > Di code saya, preprocessing timenya less than 1 second. > Dan bisa menjawab 1 juta queries dalam 5 detik. > Karena saya hanya perlu log( 1 juta ) = 20 kali looping untuk masing2 query. > > Untuk yang lain, especially Kurniady. > Coba improve code yang saya attach supaya bisa menjawab 1 juta queries > dalam 1 detik. > Katanya kan ada tuch algo O ( 1 ) nya untuk query :D > > Itu tantangan berikutnya :D > > Bagi yang ingin mempelajari code BST nya, silahkan tanya kalau tidak > dimengerti. > > Felix Halim > >