Video: 7 MACAM PROGRAMMER 2024
Fungsi matematika hanyalah cara untuk memetakan beberapa masukan ke sebuah respons. Dinyatakan dengan cara yang berbeda, fungsi adalah transformasi (berdasarkan operasi matematika) yang mengubah (memetakan) masukan Anda ke sebuah jawaban.
Untuk nilai input tertentu (biasanya dilambangkan dengan huruf x atau n), Anda memiliki jawaban yang sesuai dengan menggunakan matematika yang mendefinisikan fungsinya. Misalnya, fungsi seperti f (n) = 2 n memberi tahu Anda bahwa bila masukan Anda adalah angka n, jawaban Anda adalah bilangan n dikalikan dengan 2.
Dengan menggunakan ukuran input tidak masuk akal mengingat ini adalah zaman yang kritis dan kehidupan manusia dijejali dengan semakin banyaknya data. Membuat semua fungsi matematika sedikit kurang intuitif, namun sebuah fungsi yang menjelaskan bagaimana algoritma menghubungkan solusinya dengan jumlah data yang diterimanya adalah sesuatu yang dapat Anda analisis tanpa dukungan perangkat keras atau perangkat lunak tertentu. Ini juga mudah untuk membandingkan dengan solusi lain, mengingat ukuran masalah Anda. Analisis algoritma benar-benar konsep mind-blowing karena mengurangi serangkaian langkah kompleks menjadi formula matematika.
Selain itu, sebagian besar waktu, analisis algoritma bahkan tidak tertarik untuk menentukan fungsinya dengan tepat. Yang benar-benar ingin Anda lakukan adalah membandingkan fungsi target dengan fungsi lain. Fungsi perbandingan ini muncul dalam satu set fungsi yang diusulkan yang berkinerja buruk bila dibandingkan dengan algoritma target. Dengan cara ini, Anda tidak perlu memasukkan nomor ke fungsi kompleksitas yang lebih besar atau lebih kecil; Sebagai gantinya, Anda berurusan dengan fungsi sederhana, premade, dan terkenal. Ini mungkin terdengar kasar, tapi lebih efektif dan serupa dengan mengklasifikasi kinerja algoritma ke dalam kategori, daripada mendapatkan pengukuran kinerja yang tepat.
Kumpulan fungsi umum disebut notasi Big O, dan Anda sering menemukan kumpulan fungsi kecil ini (dimasukkan ke dalam tanda kurung dan didahului oleh sebuah modal O >) digunakan untuk mewakili kinerja algoritma. Angka tersebut menunjukkan analisis algoritma. Sistem koordinat Cartesian dapat mewakili fungsinya yang diukur dengan simulasi RAM, di mana abscissa (koordinat x) adalah ukuran input dan koordinat ordinat (koordinat y) adalah menghasilkan jumlah operasi. Anda dapat melihat tiga kurva yang diwakili. Ukuran input penting. Namun, kualitas juga penting (misalnya saat memesan masalah, lebih cepat memesan masukan yang sudah hampir dipesan).Akibatnya, analisis menunjukkan kasus terburuk, f 1 (n), kasus rata-rata, f 2 (n), dan kasus terbaik, f 3 (n). Meskipun kasus rata-rata mungkin memberi Anda gagasan umum, yang benar-benar Anda pedulikan adalah kasus terburuk, karena masalah mungkin timbul saat algoritme Anda berjuang mencapai solusi. Fungsi Big O adalah nilai setelah
n0
(ambang untuk mempertimbangkan masukan besar), selalu menghasilkan jumlah operasi yang lebih besar dengan input yang sama daripada fungsi terburuk > f1
. Dengan demikian, fungsi Big O bahkan lebih pesimis daripada yang mewakili algoritma Anda, sehingga tidak masalah kualitas inputnya, Anda bisa yakin hal itu tidak bisa menjadi lebih buruk dari itu.
Kompleksitas algoritma dalam kasus kasus masukan terbaik, rata-rata, dan terburuk.
Banyak kemungkinan fungsi dapat menghasilkan hasil yang lebih buruk, namun pilihan fungsi yang ditawarkan oleh notasi Big O yang dapat Anda gunakan dibatasi karena tujuannya adalah untuk menyederhanakan pengukuran kompleksitas dengan mengajukan standar. Akibatnya, bagian ini hanya berisi beberapa fungsi yang merupakan bagian dari notasi Big O. Daftar berikut menggambarkannya dalam urutan kompleksitas yang meningkat:
Saat yang sama, tidak peduli berapa banyak masukan yang Anda berikan. Pada akhirnya, ini adalah jumlah konstan operasi, tidak peduli berapa lama input data. Tingkat kompleksitas ini cukup langka dalam praktiknya.
- Kompleks logaritma O (log n): Jumlah operasi tumbuh pada tingkat yang lebih lambat dari pada input, membuat algoritma kurang efisien dengan input kecil dan lebih efisien dengan yang lebih besar. Algoritma khas kelas ini adalah pencarian biner.
- Kompleksitas linier O (n): Operasi tumbuh dengan input dalam rasio 1: 1. Algoritma yang khas adalah iterasi, yaitu saat Anda memindai input sekali dan menerapkan operasi ke setiap elemennya.
- Kompleksitas linier O (n log n): Kompleksitas adalah perpaduan antara kompleksitas logaritmik dan linier. Ini adalah tipikal dari beberapa algoritma cerdas yang digunakan untuk memesan data, seperti Mergesort, Heapsort, dan Quicksort.
- Kompleksitas kuadrat O (n 2
- ): Operasi tumbuh sebagai kuadrat jumlah input. Bila Anda memiliki satu iterasi di dalam iterasi lain (nested iterasi, dalam ilmu komputer), Anda memiliki kompleksitas kuadrat. Misalnya, Anda memiliki daftar nama dan, untuk menemukan yang paling mirip, Anda membandingkan setiap nama dengan semua nama lainnya. Beberapa algoritma pemesanan yang kurang efisien menyajikan kompleksitas seperti itu: sort bubble, sort sort selection, dan insertion sort. Tingkat kompleksitas ini berarti bahwa algoritma Anda dapat berjalan berjam-jam atau bahkan berhari-hari sebelum mencapai solusi. Kompleksitas kubus O (n 3
- ): Operasi tumbuh lebih cepat daripada kompleksitas kuadrat karena sekarang Anda memiliki beberapa iterasi bersarang. Ketika sebuah algoritma memiliki urutan kompleksitas ini dan Anda perlu mengolah sejumlah data sederhana (100, 000 elemen), algoritme Anda dapat berjalan selama bertahun-tahun.Bila Anda memiliki sejumlah operasi yang merupakan kekuatan input, adalah umum untuk merujuk ke algoritma sebagai yang berjalan pada waktu polinomial. Kompleksitas eksponensial O (2 n
- ): Algoritma membutuhkan dua kali jumlah operasi sebelumnya untuk setiap elemen baru ditambahkan. Ketika sebuah algoritma memiliki kompleksitas ini, masalah kecil mungkin akan terjadi selamanya. Banyak algoritma yang melakukan pencarian menyeluruh memiliki kompleksitas eksponensial. Namun, contoh klasik untuk tingkat kerumitan ini adalah perhitungan angka Fibonacci. Kompleksitas Faktorial O (n!): Mimpi buruk yang nyata karena banyaknya kemungkinan kombinasi antar elemen. Bayangkan saja: Jika input Anda 100 objek dan operasi pada komputer Anda membutuhkan 10
- -6 detik (kecepatan yang masuk akal untuk setiap komputer, saat ini), Anda memerlukan sekitar 10 140 tahun untuk menyelesaikan tugas dengan sukses (jumlah waktu yang tidak tepat sejak usia alam semesta diperkirakan berusia 10 14 tahun). Masalah kompleksitas faktorial yang terkenal adalah masalah salesman keliling, di mana seorang salesman harus menemukan rute terpendek untuk mengunjungi banyak kota dan kembali ke kota awal.
