Design and Analysis of Algorithms CNH2G3- Week 3 Notasi Asymptotic dan Kelas Dasar Efisiensi Dr. Putu Harry Gunawan (PHN)
Review 1. What the complexity of the following pseudocode x <- 0 for x <- 0 to n: for y <- 0 to n: a=c+d 2. What the complexity of the following pseudocode x <- 0 for x <- 0 to n: for y <- x to n-3: a=c+d 3. What the complexity of the following pseudocode x <- 0 for x <- 2 to n+2: for y <- x-1 to n: a=c+d
Example 0.1 Find the time complexity of the following codes for basic operation addition (+) Some algorithms have logarithmic (base 2) complexity: 1. 2. 3. 4. 5. 6.
i = n; while (i >= 1) { x = x + 1; i = i / 2; }
// i starts from n
// count this line // i becomes half at the end of every iteration
1
Iteration
value of i (at the top of loop)
number of times line 4 is executed
1 2 3 k k+1
n
1 1 1 1 0
n 21 n 22 n 2k−1 n 2k
We are interested in what k is (because that’s the number of times the line 4 is executed). In other words, T (n) = 1 + 1 + 1 + .. + 1 = (k × 1) | < − − kof them − −− > | To derive k, we look at the relation at the last iteration (kth): n =0 2k n log2 k = log2 (0) 2 log2 n − log(2k ) = log2 (0) k log2 (2) = log2 n − log2 (0) k = log2 n − 1 Thus, T (n) = log2 (n) − 1
1
Pendahuluan
Seperti yang sudah dibahas pada bab-bab sebelumnya, ruang lingkup analisis efisiensi berfokus pada naiknya orde jumlah operasi dasar sebagai indikator utama pada algoritma efisien. Untuk membandingkan tingkatan dari orde kenaikan kompleksitas waktu, Computer Scientist menggunakan tiga notasi berikut: 1. O (big oh), 2. Ω (big omega), dan 3. Θ (big theta). Dalam tulisan ini, pengenalan notasi di atas akan disampaikan secara tidak formal(informal ) dalam beberapa contoh dan kemudian secara formal dalam bentuk definisi. Untuk materi selanjutnya kan diperkenalkan notasi: 1. Fungsi t(n) dan g(n) merupakan fungsi tidak negatif terdefinisi pada himpunan bilangan asli. 2. Fungsi t(n) akan berupa waktu dari berjalannya algoritma (yang biasanya terindikasi pada jumlah operasi dasar C(n)). 3. Fungsi g(n) akan berupa beberapa contoh fungsi yang digunakan sebagai perbandingan.
2
2
Pengantar tidak formal (informal )
Secara tidak formal, O(g(n)) merupakan sebuah himpunan semua fungsi yang orde kenaikannya (order of growth) berada di bawah atau sama dengan fungsi orde kenaikan g(n). Sebagai contoh: 1. n ∈ O(n2 ), 2. 100n + 5 ∈ O(n2 ), 3.
1 2 n(n
− 1) ∈ O(n2 ).
Jelas bahwa dua fungsi pertama adalah fungsi linier sehingga memiliki orde di bawah orde kenaikan fungsi g(n) = n2 . Sedangkan fungsi ke-tiga merupakan fungsi kuadratik yang memiliki orde kenaikan sama dengan fungsi n2 . Dilain pihak, 1. n3 ∈ / O(n2 ), 2. 0.000001n3 ∈ / O(n2 ), 3. n4 + n + 1 ∈ / O(n2 ). Jelas bahwa, fungsi n3 dan 0.000001n3 merupakan fungsi kubik yang memiliki orde kenaikan lebih dari n2 . Begitu pula dengan polinomial n4 + n + 1 memiliki orde kenaikan orde empat. Notasi ke-dua Ω(g(n)), menyatakan himpunan dari semua fungsi yang memiliki orde kenaikan lebih besar atau sama dengan g(n). Sebagai comtoh: 1. n3 ∈ Ω(n2 ), 2.
1 2 n(n
− 1) ∈ Ω(n2 ), tetapi
3. 100n + 5 ∈ / Ω(n2 ). Terakhir, Θ(g(n)) merupakan himpunan semua fungsi yang memiliki orde kenaikan sama dengan g(n). Contoh semua fungsi kuadratik an2 + bn + c dengan a > 0 berada pada Θ(n2 ). Hal ini juga terjadi pada fungsi lain seperti n2 + sin n dan n2 + log n, kenapa?
3 3.1
Formal Definition Notasi O
Definition 3.1 Sebuah fungsi t(n) dikatakan berada dalam O(g(n)), dinotasikan sebagai t(n) ∈ O(g(n)), jika t(n) terbatas di atas oleh suatu konstanta positif dikalikan dengan fungsi g(n) untuk n yang terus membesar. Atau dapat dikatakan bahwa terdapat beberapa konstanta positif c dan beberapa bilangan bulat tak-negatif n0 sehingga t(n) ≤ cg(n)
for all n ≥ n0 .
Dapat diilustrasikan melalui Gambar 1.
3
(3.1)
Figure 1: Notasi Big-Oh: t(n) ∈ O(g(n)).
Example 3.2 Mari kita buktikan secara formal 100n + 5 ∈ O(n2 ). Jelas bahwa 100n + 5 ≤ 100n + 5(untuk semua n ≥ 5), = 101n ≤ 101n2 . Sehingga terbukti terdapat c = 101 dan n0 = 5. Catatan bahwa, definisi memberikan sembarang nilai c dan n0 , sehingga terdapat cara lain untuk membuktikan, yaitu 100n + 5 ≤ 100n + 5n(untuk semua n ≥ 1), = 105n ≤ 105n2 . Sehingga terbukti dengan c = 105 dan n0 = 1.
3.2
Notasi Ω
Definition 3.3 Sebuah fungsi t(n) dikatakan berada dalam Ω(g(n)), dinotasikan sebagai t(n) ∈ Ω(g(n)), jika t(n) terbatas di bawah oleh suatu konstanta positif dikalikan dengan fungsi g(n) untuk n yang terus membesar. Atau dapat dikatakan bahwa terdapat beberapa konstanta positif c dan beberapa bilangan bulat tak-negatif n0 sehingga t(n) ≥ cg(n)
untuk setiap n ≥ n0 .
Dapat diilustrasikan melalui Gambar 2. Example 3.4 Akan dibuktikan bahwa n3 ∈ Ω(n2 ): n3 ≥ n2 untuk semua n ≥ 0. Sehingga terbukti dengan c = 1 dan n0 = 0.
4
(3.2)
Figure 2: Notasi Big-Omega: t(n) ∈ Ω(g(n)).
3.3
Notasi Θ
Definition 3.5 Sebuah fungsi t(n) dikatakan berada dalam Θ(g(n)), dinotasikan sebagai t(n) ∈ Θ(g(n)), jika t(n) terbatas di atas dan bawah oleh suatu konstanta positif dikalikan dengan fungsi g(n) untuk n yang terus membesar. Atau dapat dikatakan bahwa terdapat beberapa konstanta positif c1 dan c2 dan beberapa bilangan bulat tak-negatif n0 sehingga c2 g(n) ≤ t(n) ≤ c1 g(n)
untuk setiap n ≥ n0 .
(3.3)
Dapat diilustrasikan melalui Gambar 3.
Figure 3: Notasi Big-Theta: t(n) ∈ Θ(g(n)).
Example 3.6 Akan dibuktikan bahwa 12 n(n−1) ∈ Θ(n2 ). Perta akan dibuktikan untuk pertaksamaan sebelah kanan (batas atas): 1 1 1 1 n(n − 1) = n2 − n ≤ n2 untuk semua n ≥ 0. 2 2 2 2
5
Kedua, akan dibuktikan pertaksamaan sebelah kiri (batas bawah) 1 1 1 n(n − 1) = n2 − n ≥ 2 2 2 1 2 1 1 1 n − n n untuk semua n ≥ 2. = n2 2 2 2 4 Sehingga terbukti dengan c2 = 14 , c1 =
4
1 2
dan n0 = 2.
Properti notasi asimptotik
Theorem 4.1 Jika diberikan fungsi polinomial berderajan m, T (n) = am nm +am − 1nm−1 + · · · + a1 n + a0 maka T (n) ∈ O(nm ). Theorem 4.2 Andaikan T1 (n) ∈ O(f (n)) and T2 (n) ∈ O(g(n)), maka 1. T1 (n) + T2 (n) ∈ O(f (n)) + O(f (n)) ∈ O(max(f (n), g(n))) 2. T1 (n)T2 (n) ∈ O(f (n))O(g(n)) = O(f (n)g(n)) 3. O(cf (n)) = cO(f (n)), c adalah sembarang konstanta 4. f (n) ∈ O(f (n))
Example 4.3 Misalkan T1 (n) ∈ O(n) dan T2 (n) ∈ O(n2 ) , maka 1. T1 (n) + T2 (n) ∈ O(max(n, n2 )) = O(n2 ) 2. T1 (n)T2 (n) = O(n · n2 ) = O(n3 )
Example 4.4 O(5n2 ) = O(n2 )
Example 4.5 Diketahui T (n) = (n + 2) log(n2 + 1) + 5n2 maka kompleksitas waktu O(n)-nya adalah? Misalkan T (n) = (n + 2) log(n2 + 1) + 5n2 = f (n)g(n) + h(n) Dengan pencarian satu-satu didapat: 1. f (n) = (n + 2) ∈ O(n) 2. g(n) = log(n2 + 1), karena log(n2 + 1) ≤ log(2n2 ) = log 2 + log n2 = log 2 + 2 log n ≤ 3 log n untuk n > 2
6
3. h(n) = 5n2 ∈ O(n2 ) Maka, T (n) = (n + 2) log(n2 + 1) + 5n2 ∈ O(n)O(log n) + O(n2 ) = O(n log n) + O(n2 ) = O(max(n log n, n2 )) = O(n2 )
5
Kelas Dasar Efisiensi
Berikut adalah tabel kelas dasar efiseinsi: Kelas
Nama
1
constant
log n
logarithmic
n
linear
n log n
linearithmic
Komentar Efisinsi kasus terbaik. Kompleksitas O berarti waktu pelaksanaan algoritma adalah tetap, tidak bergantung pada ukuran masukan. Kompleksitas waktu logaritmik berarti laju pertumbuhan waktunya berjalan lebih lambat daripada pertumbuhan n. Algoritma yang termasuk kelompok ini adalah algoritma yang memecahkan persoalan besar dengan mentransformasikannya menjadi beberapa persoalan yang lebih kecil yang berukuran sama (misalnya algoritma pencarian biner). Algoritma yang waktu pelaksanaannya lanjar umumnya terdapat pada kasus yang setiap elemen masukannya dikenai proses yang sama, misalnya algoritma pencarian beruntun. Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma juga dua kali semula. Waktu pelaksanaan yang n log n terdapat pada algoritma yang memecahkan persoalan menjadi beberapa persoalan yang lebih kecil, menyelesaikan tiap persoalan secara independen, dan menggabung solusi masing- masing persoalan.
7
n2
quadratic
n3
cubic
2n
exponential
n!
factorial
Algoritma yang waktu pelaksanaannya kuadratik hanya praktis digunakan untuk persoalan yang berukuran kecil. Umumnya algoritma yang termasuk kelompok ini memproses setiap masukan dalam dua buah looping bersarang, misalnya pada algoritma urut maks. Seperti halnya algoritma kuadratik, algoritma kubik memproses setiap masukan dalam tiga buah looping bersarang, misalnya algoritma perkalian matriks. Algoritma yang tergolong kelompok ini mencari solusi persoalan secara ”brute force”, misalnya pada algoritma mencari sirkuit Hamilton. Seperti halnya pada algoritma eksponensial, algoritma jenis ini memproses setiap masukan dan menghubungkannya dengan n−1 masukan lainnya, misalnya algoritma Persoalan Pedagang Keliling (Travelling Salesperson Problem).
Nilai masing-masing fungsi untuk kenaikan n. log n
n
n log n
n2
n3
2n
n!
0 0.3010299957 0.6020599913 0.9542425094 1.2041199827 1.5051499783
1 2 4 9 16 32
0 0.6020599913 2.4082399653 8.588182585 19.2659197225 48.1647993062
1 4 16 81 256 1024
1 8 64 729 4096 32768
2 4 16 512 65536 4294967296
1 2 24 362880 20922789888000 2.63130836933694E+035
Figure 4: Nilai masing-masing fungsi untuk kenaikan n.
6
Menggunakan Limit untuk membnadingkan orde kenaikan
Untuk mempermudah mengidentifikasi kompleksitas waktu O, Ω dan Θ, maka cara membandingkan dapat pula dilakukan. 8
Definition 6.1 Terdapat tiga kasus utama dalam membandingkan waktu komputasi: 0, artinya t(n) memiliki orde lebih rendah dari g(n) t(n) = lim c, artinya t(n) memiliki orde sama dengan g(n) n→∞ g(n) ∞, artinya t(n) memiliki orde lebih tinggi dari g(n) Catatan bahwa dua kasus pertama mengidentifikasikan t(n) ∈ O(g(n)), dua kasus terakhir mengidentifikasikan t(n) ∈ Ω(g(n)) dan kasus ke-dua mengidentifikasikan t(n) ∈ Θ(g(n))
Example 6.2 Bandingkan orde kenaikan 12 n(n − 1) dan n2 . lim
n→∞
1 2 n(n
− 1)
n2
=
1 n2 − n 1 1 1 lim = lim (1 − ) = 2 n→∞ n→∞ 2 n 2 n 2
Karena hasil limitnya merupakan konstanta positif, yang berarti bahwa memiliki orde sama, maka dapat dinotasikan sebagai 12 n(n − 1) ∈ Θ(n2 ).
References 1. Anany, L. (2003). Introduction to the design and analysis of algorithms. Villanova University. 2. http://www.annedawson.net/BigOh.htm
7
Exercise 1. Tentukan notasi Ω dan Θ untuk T (n) = 2n2 + 6n + 1. 2. Tentukan notasi O, Ω dan Θ untuk T (n) = 5n3 + 6n2 log n. 3. Tentukan notasi O, Ω dan Θ untuk T (n) = 1 + 2 + · · · + n. 4. Tentukan notasi O untuk T (n) = 2 + 4 + · · · + 2n. 5. Tentukan notasi O untuk T (n) = (n + 1)(n + 3)/(n + 2). 6. Tentukan notasi O, Ω dan Θ dari pseudocode x <- 0 for x <- 0 to n: for y <- 0 to n: a=c+d 7. Tentukan notasi O, Ω dan Θ dari pseudocode x <- 0 for x <- 0 to n: for y <- x to n-3: a=c+d 9
8. Tentukan notasi O, Ω dan Θ dari pseudocode x <- 0 for x <- 2 to n+2: for y <- x-1 to n: a=c+d 9. Tentukan notasi O, Ω dan Θ dari masalah berikut • Consider the problem of finding the value of the largest element in a list of n numbers. For simplicity, we assume that the list is implemented as an array. The following is pseudocode of a standard algorithm for solving the problem. ALGORITHM MaxElement(A[0..n 1]) //Determines the value of the largest element in a given array //Input: An array A[0..n 1] of real numbers //Output: The value of the largest element in A maxval <-- A[0] for i <-- 1 to n - 1 do if A[i] > maxval maxval <-- A[i] return maxval • Consider the element uniqueness problem: check whether all the elements in a given array of n elements are distinct. This problem can be solved by the following straightforward algorithm. ALGORITHM UniqueElements(A[0..n 1]) //Determines whether all the elements in a given array are distinct //Input: An array A[0..n 1] //Output: Returns true if all the elements in A are distinct // and false otherwise for i <-- 0 to n - 2 do for j <-- i + 1 to n - 1 do if A[i] = A[j] return false return true • Given two n × n matrices A and B, find the time efficiency of the definitionbased algorithm for computing their product C = AB. By definition, C is an n × n matrix whose elements are computed as the scalar (dot) products of the rows of matrix A and the columns of matrix B. ALGORITHM MatrixMultiplication(A[0..n 1, 0..n 1], B[0..n 1, 0..n 1]) //Multiplies two square matrices of order n by the definition-based algorithm //Input: Two n n matrices A and B //Output: Matrix C = AB for i <-- 0 to n - 1 do for j <-- 0 to n - 1 do C[i, j ] <-- 0.0 for k 0 to n 1 do C[i, j] <-- C[i, j] + A[i, k] * B[k, j] return C 10
• Binary search algorithm. Procedure binary_search A sorted array n size of array x value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound - lowerBound ) / 2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint - 1 if A[midPoint] = x EXIT: x found at location midPoint end while end procedure
11
