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
