sory double posting keteken send waktu gambar2 BStnya
preprocess bikin:
- binary search tree (left selalu lebih kecil dari parent, kanan selalu lebih
gede dari parent)
tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya
untuk array ini: [2,4,1,3]
BST value-nya:
2
/ \
1
4
/
3
BST indexnya:
0
/ \
2 1
/
3
tuk bikin BST dari array yang sudah ada kira2: O(n)
searchnya pake algo kira2 begini:
- search on left,
kalo belum ktemu search on right
kalo udah ktemu terus search on left (cari terus ke node left paling
dalam yang bisa ditemukan note: node right engga usah disearch)
jadi tuk search:
queryMin( 0, 3 ) =
- ktemu 0, keep on searching left
- ktemu 2 keep on searching left which is null
so hasilnya = 2
queryMin( 1, 1 ) =
- 0, belum ktemu cari kiri
- 2 belum ktemu kiri, kanan ga ada
- recursif back to 0, kanannya 1
- 1 ktemu, cari kiri null
hasil = 1
queryMin( 1, 2 ) = 1
- 0 belum ktemu, cari kiri
- 2 ktemu cari kiri, null
hasil=2
queryMin( 0, 1 ) = 2
- 0 ktemu, keep kiri
- kiri = 2, tidak ada di index balek ke parent
hasil = 0
queryMin( 3, 3 ) =
- 0 belum ktemu cari kiri
- kiri =2 tidak ada di index balek parent search kanan
- 1 belum ktemu cari kiri = null
- cari kanan, ktemu =3, keep kiri = null
- hasil = 3
searchnya kira2 = O(log n)
regards,
yohan
--- On Sat, 6/7/08, Felix Halim <[EMAIL PROTECTED]> wrote:
From: Felix Halim <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Saturday, June 7, 2008, 1:45 PM
2008/6/7 Hendry <[EMAIL PROTECTED] com>:
> soal ini kamu yang bikin? atau penjelasan berikut ini based on your
assumption?
> kalau kamu yang bikin, i got no further questions, tapi kalau hanya
> based on assumption, seperti nya arti dan maksud dari soal dan
> penjelasan yang diberikan berikut sudah berbeda.
Soal ini adalah soal classic (sudah ada dari jaman dahulu), jadi bukan
saya yang bikin.
Yang research solusinya juga banyak (banyak scientific paper ttg problem ini).
Hmm... saya tulis ulang deh problemnya, sepertinya kurang jelas:
Diberikan array of integer A yang isinya adalah bilangan integer acak
sebanyak N elements.
Saya ingin query bilangan integer terkecil dari array A yang index nya
antara i dan j (inclusive).
Index dari array adalah 0-based (index dimulai dari angka 0).
Untuk memprocess tiap query, harus tidak lebih dari O ( log N ) steps.
Tapi query ini bisa banyak kali (querynya bukan cuman satu kali).
Dan anda diperbolehkan untuk preprocess array A terlebih dahulu tapi
tidak lebih dari O ( N log N ) steps.
Semoga tidak ada keambiguan lagi.
2008/6/7 viking leon <[EMAIL PROTECTED] com>:
> preprocessnya pake
> - merge sort = O(n log n)
Begitu kamu sort, array indexnya berantakan.
> selanjutnya search bilangan pake
> - binary search = O (log n)
> kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time
O(1)
Querynya adalah "cari bilangan terkecil antara index i dan index j di array A"
Kalau kamu sort, maka index i dan j nya sudah berantakan, maka
hasilnya akan salah.
Apakah masih blum jelas tentang hal ini?
2008/6/7 Hendry Luk <[EMAIL PROTECTED] com>:
> napa gak preprocessnya langsung swap bilangan terkecil ke paling depan?
> O(n), lebih efisien drpd merge sort O(n log n).
>
> Selanjutnya. .. searchnya... .. array[0] ;) .... O(1)
>
> Gw gak ngerti nih batasan preprocessingnya
Ok, contoh berikut mungkin akan lebih jelas:
A = [ 2, 4, 1, 3 ]
queryMin( 0, 3 ) = 1 // nilai terkecil di array A antara index 0..3
adalah 1 (dengan index 3)
queryMin( 1, 1 ) = 4 // nilai terkecil di array A antara index 1..1
adalah 4 (dengan index 1)
queryMin( 1, 2 ) = 1 // nilai terkecil di array A antara index 1..2
adalah 1 (dengan index 3)
queryMin( 0, 1 ) = 2 // nilai terkecil di array A antara index 0..1
adalah 2 (dengan index 0)
queryMin( 3, 3 ) = 3 // nilai terkecil di array A antara index 3..3
adalah 3 (dengan index 3)
Kalau kamu sort array A, maka indexnya semua akan berantakan, dan
hasilnya akan salah:
A = [ 1, 2, 3, 4 ]
queryMin( 0, 3 ) = 1 // nilai terkecil di array A antara index 0..3
adalah 1 (dengan index 3) (ok ini benar)
queryMin( 1, 1 ) = 2 // nilai terkecil di array A antara index 1..1
adalah 2 (dengan index 1) (ini SALAH)
queryMin( 1, 2 ) = 1 // nilai terkecil di array A antara index 1..2
adalah 2 (dengan index 1) (ini SALAH)
queryMin( 0, 1 ) = 2 // nilai terkecil di array A antara index 0..1
adalah 1 (dengan index 0) (ini SALAH)
queryMin( 3, 3 ) = 3 // nilai terkecil di array A antara index 3..3
adalah 4 (dengan index 3) (ini SALAH)
Query pertama mungkin benar, tapi query ke dua dan seterusnya akan salah.
Karena indexnya setelah disort, bukan lagi index AWAL dari array A semula.
Sedangkan query yang diminta adalah index AWAL dari array A.
Felix Halim
