O(log N) artinya apa Felix ? Maksudnya dengan N = 10, looping harus cuma log 10 = 1 ?
Regards, Feris 2008/6/6 Felix Halim <[EMAIL PROTECTED]>: > Cara itu terkenal dengan nama Dynamic Programming. > > Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming > Contest. > > Ini ada problem yang lebih menantang: > > Diberikan array of integer A (0-based index). > Saya ingin mencari bilangan integer terkecil di array A dengan index > antara [i, j] (inclusive). > Jawabannya harus dalam O ( log N ) > > Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ). > Ada yang bisa? > > Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest. > > FYI, Google suka orang2 yang tahu banyak algorithms ;) > Makanya Google ngadain "Google Code Jam" tiap tahun. > > Milis yang membahas Programming Contest di indo itu: > > http://groups.yahoo.com/group/indo-algo > > Tapi sepi nih... disini malah seru :D, bener2 aneh... > > Felix Halim > > > On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo <[EMAIL > PROTECTED]<jecki.go%40gmail.com>> > wrote: > > On Fri, Jun 6, 2008 at 3:16 PM, naray citra <[EMAIL > > PROTECTED]<naray_citra%40yahoo.com>> > wrote: > >> Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang > butuh > >> :D > >> sumber : http://linkmingle.com/details/865 > >> > >> There is an array A[N+1] of N integers. You have to compose an array > >> Output[N+1] such that Output[i] will be equal to the productof all the > >> elements of A[] except A[i]. > >> Example: > >> INPUT:[4, 3, 2, 1, 2] > >> OUTPUT:[12, 16, 24, 48, 24] > >> > >> Solve it without division operator and in O(n) with out using division > >> > >> import java.util.Arrays; > >> > >> public class PArray { > >> > >> public int[] PSub(int[] inp){ > >> int[] out = new int[inp.length]; > >> out[0]=1;out[1]=inp[0]; > >> for (int i = 2; i <inp.length ; i++) > >> out[i] = inp[i-1]*out[i-1]; > >> int P = 1; > >> for(int i=inp.length-2;i>=0;i--){ > >> P*=inp[i+1]; > >> out[i]=out[i]*P; > >> } > >> return out; > >> } > >> public static void main(String[] args) { > >> PArray pArray = new PArray(); > >> int in[] = new int[]{4,3,2,1,2}; > >> System.out.println("INPUT:"+ > >> Arrays.toString(in)); > >> System.out.println("OUTPUT:"+ > >> Arrays.toString(pArray.PSub(in))); > >> } > >> } > >> > > > > Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2) > > soalnya ada inner loop yg jumlahnya mendekati n. CMIIW. > > > > Seru juga. Masih blom ketemu caranya nih :) > > > > ------------------------------------ > > > > Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke > [EMAIL PROTECTED]<jug-indonesia-unsubscribe%40yahoogroups.com> > . > > > > Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id > > > > Yahoo! Groups Links > > > > > > > > > > -- Thanks & Best Regards, Feris PT. Putera Handal Indotama A Business Intelligence Company Jl. K.H. Moh Mansyur No. 11 B 8 - 12 Jakarta - Indonesia Phone : +6221-30119353 Fax : +6221-5513483 Mobile : +628176-474-525 http://business-intelligence.phi-integration.com http://blog.komputasiawan.com
