Ada kayaknya deh, di text itu nyebutnya "Sparse Table (ST) algorithm". Kalau punya Felix itu Segment-tree. Bener gak?
TreeNode loe nggak bersih 40mb lix kayaknya, kan itu Class/Object, jadi kayaknya masih ada overheadnya juga. -Kurniady 2008/6/11 Felix Halim <[EMAIL PROTECTED]>: > 2008/6/11 Feris Thia <[EMAIL PROTECTED]>: > >> Untuk pemakaian algoritma yang eksekusinya optimal seperti ini memang >> memori >> harus besar untuk preprocessnya ya ? Belum baca teorinya sih, tapi pas >> eksekusi code dari Felix dan Andrian saya harus menambah heap size nya :p > > Bisa dihitung kok pemakaian memorynya: > > public static final int[] A = new int[N]; > public static final int[][] B = new int[22][N]; > public static final int[] lvmat = new int[1000010]; > public static final int[] duapang = new int[30]; > > Space nya sekitar O ( N log N ). > Sekitar 96 MB. ( 24 * 1 juta * 4 byte = 96 MB ) > > Kalau pake BST, spacenya sekitar O ( N ). > Sekitar 40 MB. (setiap node ada 5 values dan total ada 2N nodes, jadi > 10N space = 10 * 1 juta * 4 byte = 40 MB) > > Blum saya test pake profiler sih bener apa kaga. > Secara teori harusnya sekitar situ plus minus temporary variables + call > stack. > > 2008/6/11 Kong Putra <[EMAIL PROTECTED]>: >> Sekedar info.., dari hasil googling... :) >> >> >> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor > > Tidak perlu baca artikel itu pun harusnya bisa kok solve soal RMQ ini. > Kalau dilihat sekelebatan, sepertinya solusi O( 1 ) nya si Andrian > Kurniady tidak ada di artikel tersebut :P > Bener gak kur? coba di cek deh... > > Felix Halim
