Kompleksitas waktu

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.