- Tinjau T(n) = 2n2 + 6n + 1
| n | T(n) = 2n2 + 6n + 1 | n2 |
| 10 100 1000 10.000 | 261 2061 2.006.001 2.000.060.001 | 100 1000 1.000.000 1.000.000.000 |
- Untuk n yang besar, pertumbuhan T(n) sebanding dengan n2. Pada kasus ini, T(n) tumbuh seperti n2 tumbuh.
- T(n) tumbuh seperti n2 tumbuh saat n bertambah. Kita katakan bahwa T(n) berorde n2 dan kita tuliskan: T(n) = O(n2)
DEFINISI. T(n) = O(f(n)) (dibaca “T(n) adalah O(f(n))” yang artinya T(n) berorde paling besar f(n) ) bila terdapat konstanta C dan n0 sedemikian sehingga
T(n) C(f (n))
untuk n n0.
f(n) adalah batas lebih atas (upper bound) dari T(n) untuk n yang besar.
Penjelasan masing-masing kelompok algoritma adalah sebagai berikut:
O(1) :
Kompleksitas O(1) berarti waktu pelaksanaan algoritma adalah tetap, tidak bergantung pada ukuran masukan.
Contohnya prosedur tukar di bawah ini:
procedure tukar(var a:integer; var b:integer);
var
temp:integer;
begin
temp:=a;
a:=b;
b:=temp;
end;
Di sini jumlah operasi penugasan (assignment) ada tiga buah dan tiap operasi dilakukan satu kali. Jadi, T(n) = 3 = O(1). O(log n) :
Kompleksitas waktu logaritmik berarti laju pertumbuhan waktunya berjalan lebih lambat daripada pertumbuhan n.Algoritma yang termasuk kelompok ini adalah algoritmayang memecahkan persoalan besar denganmentransformasikannya menjadi beberapa persoalan yanglebih kecil yang berukuran sama (misalnya algoritma pencarian_biner). Di sini basis algoritma tidakterlalu penting sebab bila n dinaikkan dua kali semula, misalnya, log n meningkat sebesar sejumlah tetapan.
O(n) :
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.
O(n log n) :
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 masingmasing persoalan. Algoritma yang diselesaikan dengan teknik bagi dan gabung mempunyai kompleksitas asimptotik jenis ini. Bila n = 1000, maka n log n mungkin 20.000. Bila n dijadikan dua kali semual, maka n log n menjadi dua kali semula (tetapi tidak terlalu banyak).
O(n2) :
Algoritma yang waktu pelaksanaannya kuadratik hanya praktis digunakan untuk persoalana yang berukuran kecil. Umumnya algoritma yang termasuk kelompok ini memproses setiap masukan dalam dua buah kalang bersarang, misalnya pada algoritma urut_maks. Bila n = 1000, maka waktu pelaksanaan algoritma adalah 1.000.000. Bila n dinaikkan menjadi dua kali semula, maka waktu pelaksanaan algoritma meningkat menjadi empat kali semula.
O(n3) :
Seperti halnya algoritma kuadratik, algoritma kubik memproses setiap masukan dalam tiga buah kalang bersarang, misalnya algoritma perkalian matriks. Bila n = 100, maka waktu pelaksanaan algoritma adalah 1.000.000. Bila n dinaikkan menjadi dua kali semula, waktu pelaksanan algoritma meningkat menjadi delapan kali semula.
O(2n) :
Algoritma yang tergolong kelompok ini mencari solusi persoalan secara “brute force”, misalnya pada algoritma mencari sirkuit Hamilton. Bila n = 20, waktu pelaksanaan algoritma adalah 1.000.000. Bila n dijadikan dua kali semula, waktu pelaksanaan menjadi kuadrat kali semula!
O(n!) :
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 . Bila n = 5, maka waktu
pelaksanaan algoritma adalah 120. Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma menjadi faktorial dari 2n.
Contoh 6. Tunjukkan bahwa T(n) = 3n + 2 = O(n).
Penyelesaian:
3n + 2 = O(n)
karena
3n + 2 3n + 2n = 5n untuk semua n 1 (C = 5 dan n0 = 1).
Contoh 7. Tunjukkan bahwa T(n) = 2n2 + 6n + 1 = O(n2).
Penyelesaian:
2n2 + 6n + 1 = O(n2) karena
2n2 + 6n + 1 2n2 + 6n2 + n2 = 9n2 untuk semua n 1 (C =9 dan n0 = 1).
atau karena
2n2 + 6n + 1 n2 + n2 + n2 = 3n2 untuk semua n 6 (C =3 dan n0 = 6).
Contoh 8. Tentukan notasi O untuk T(n) = 2n + 3 log(n)
Penyelesaian:
2n + 3 log(n) £ 2n + 3n = 5n (untuk n ³ 1)
Jadi, T(n) = 2n + 3 log(n) = O(n)
Contoh 10: Tentukan notasi O untuk T(n) = log(n2 + 1).
Penyelesaian:
log(n2 + 1) £ log(n2 + n2) untuk n ³ 1 = log(n2) = 2 log(n)
Jadi, T(n) = log(n2 + 1) = O(log n)
Contoh 11. Tentukan notasi O untuk T(n) = log (n!)
Penyelesaian:
log(n!) = log(1 . 2 … . n) = log(1) + log(2) + … + log(n – 1) + log (n) £ log(n) + log(n) + … + log(n) = n log(n)
Jadi, T(n) = log(n!) = O(n log (n))
Contoh 12: Tentukan notasi O untuk
T(n) = 1k + 2k + … + nk
Penyelesaian:
1k + 2k + … + nk £ nk + nk + … + nk = n . nk+1
Jadi, T(n) = 1k + 2k + … + nk = O(nk+1)
Perhatikan, bahwa karena notasi O-besar menunjukkan batas fungsi lebih atas (upper-bound function), maka tidak ditentukan seberapa besar batas atas itu.
Jadi, T(n) = 2 + 3n =O(n)
T(n) = 2 + 3n = O(n2) juga benar
T(n) = 2 + 3n =O(n3) juga benar, dst
Tetapi, agar notasi O-besar bermakna, maka dalam praktek kita memilih fungsi f(n) sekecil mungkin. Jadi, kita menulis:
T(n) = 2 + 3n =O(n), bukan O(n2)
Suatu masalah dikatakan tractable (mudah dari segi komputasi) jika ia dapat diselesaikan dengan algoritma yang memiliki kompleksitas polinomial kasus terburuk (artinya dengan algoritma yang mangkus), karena algoritma akan menghasilkan solusi dalam waktu yang lebih pendek. Sebaliknya, sebuah masalah dikatakan intractable (sukar dari segi komputasi) jika tidak ada algoritma yang mangkus untuk menyelesaikannya.
Masalah yang sama sekali tidak memiliki algoritma untuk memecahkannya disebut masalah tak-terselesaikan (unsolved problem). Sebagai contoh, masalah penghentian (halting problem) jika diberikan program dan sejumlah masukan, apakah program tersebut berhenti pada akhirnya.
Kebanyakan masalah yang tidak dapat dipecahkan dipercaya tidak memiliki algoritma penyelesaian dalam kompleksitas waktu polinomial untuk kasus terburuk, karena itu dianggap intractable. Tetapi, jika solusi masalah tersebut ditemukan, maka solusinya dapat diperiksa dalam waktu polinomial. Masalah yang solusinya dapat diperiksa dalam waktu polinomial dikatakan termasuk ke dalam kelas NP (nondeterministic polynomial). Masalah yang tractable termasuk ke dalam kelas P (polynomial). Jenis kelas masalah lain adalah kelas NP-lengkap (NP-complete). Kelas masalah NP-lengkap memiliki sifat bahwa jika ada sembarang masalah di dalam kelas ini dapat dipecahkan dalam waktu polinomial, berarti semua masalah di dalam kelas tersebut dapat dipecahkan dalam waktu polinomial. Atau, jika kita dapat membuktikan bahwa salah satu dari masalah di dalam kelas itu intractable, berarti kita telah membuktikan bahwa semua masalah di dalam kelas tersebut intractable. Meskipun banyak penelitian telah dilakukan, tidak ada algoritma dalam waktu polinomial yang dapat memecahkan masalah di dalam kelas NP-lengkap. Secara umum diterima, meskipun tidak terbuktikan, bahwa tidak ada masalah di dalam kelas NPlengkap yang dapat dipecahkan dalam waktu polinomial.
No comments:
Post a Comment