Kalau nyari angka terkecil, harus O(log n), berarti pake cara yg sama seperti binary search
2008/6/6 sm96 <[EMAIL PROTECTED]>: > O(log N) itu contohnya algoritma binary search, dan quick sort O(n log n) > O(log N) cenderung lebih cepat dibanding O(n) > > 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]> wrote: >>> On Fri, Jun 6, 2008 at 3:16 PM, naray citra <[EMAIL PROTECTED]> 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] >>> >>> Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id >>> >>> Yahoo! Groups Links >>> >>> >>> >>> >> > > > > -- > syaiful.mukhlis > gtalk:[EMAIL PROTECTED] > -- syaiful.mukhlis gtalk:[EMAIL PROTECTED]
