Kompleksitas waktu

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Sed ut perspiciatis, unde omnis iste natus error sit voluptatem accusantium doloremque laudantium, totam rem aperiam eaque ipsa, quae ab illo inventore veritatis et quasi architecto beatae vitae dicta sunt, explicabo. Nemo enim ipsam voluptatem, quia voluptas sit, aspernatur aut odit aut fugit, sed quia consequuntur magni dolores eos, qui ratione voluptatem sequi nesciunt, neque porro quisquam est,

Dalam ilmu komputer, kompleksitas waktu adalah kompleksitas komputasi yang mengggambarkan sejumlah waktu komputer yang dibutuhkan untuk menjalankan suatu algoritme. Kompleksitas waktu biasanya diperkirakan dengan menghitung jumlah operasi dasar yang dilakukan oleh algoritme, dengan assumsi bahwa setiap operasi dasar membutuhkan sejumlah waktu yang sama untuk dijalankan. Dengan demikian, jumlah waktu yang dibutuhkan dan jumlah operasi dasar yang dilakukan oleh algoritme diangggap terkait dengan faktor konstan.

Karena waktu berjalannya algoritme dapat bervariasi di antara input berbeda dengan ukuran yang sama, seseorang biasanya mempertimbangkan kompleksitas waktu terburuk, yang merupakan jumlah waktu maksimum yang diperlukan untuk input dengan ukuran tertentu. Pada suatu kasus yang tidak biasa terjadi, dan biasanya ditentukan secara eksplisit, adalah kompleksitas rata-rata, yang merupakan rata-rata waktu yang dibutuhkan pada input dengan ukuran tertentu. Kondisi ini masuk akal karena jumlah input yang mungkin untuk dikerjakan dapat dihitung dan jumlahnya terbatas. Dalam kedua kasus, kompleksitas waktu umumnya dinyatakan sebagai fungsi dari ukuran input. ^:226Karena fungsi ini umumnya sulit untuk dihitung secara tepat, dan waktu proses untuk input yang kecil biasanya tidak konsekuen, seseorang biasanya berfokus pada perilaku kompleksitas tertentu ketika ukuran input meningkat—perilaku asimtotik dari kompleksitas. Oleh karena itu, kompleksitas waktu biasanya dinyatakan menggunakan notasi O besar, biasanya $O(n)$, $O(n\log n)$, $O(n^{\alpha })$, $O(2^{n})$, dll., di mana n adalah ukuran dalam satuan bit yang diperlukan untuk mewakili input.

Kompleksitas algoritma diklasifikasikan menurut jenis fungsi yang muncul dalam notasi O besar. Misalnya, algoritma dengan kompleksitas waktu $O(n)$ adalah algoritma waktu linier dan algoritma dengan kompleksitas waktu $O(n^{\alpha })$ untuk beberapa konstanta $\alpha >1$ adalah algoritma waktu polinomial.