My first Magazine pemrograman-kompetitif-dasar | Page 34

2 Matematika Diskret Dasar
Dalam dunia pemrograman, kadang kala dibutuhkan perhitungan seluruh nilai C r n yang meme-
nuhi n ≤ N, untuk suatu N tertentu. Pencarian nilai dari C r n dengan menghitung faktorial memiliki
kompleksitas O(n). Apabila seluruh nilai kombinasi dicari dengan cara tersebut, kompleksitas
n−1
akhirnya adalah O(N 3 ). Namun, dengan menggunakan persamaan C r n = C r−1
+C r n−1 , maka secara
keseluruhan kompleksitasnya dapat menjadi O(N 2 ).
Algoritma 9 merupakan implementasi untuk pencarian seluruh nilai kombinasi C r n yang
memenuhi n ≤ N, untuk suatu N.
Algoritma 9 Penggunaan Segitiga Pascal untuk mencari kombinasi.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
24
procedure PRECOMPUTE C OMBINATION (N)
C ← new integer[N + 1][N + 1]
for i ← 0, N do
C[i][0] ← 1
for j ← 1, i − 1 do
C[i][ j] = C[i − 1][ j − 1] +C[i − 1][ j]
end for
C[i][i] ← 1
end for
end procedure
. Sediakan C berukuran (N + 1) × (N + 1)