Kompleksitas algoritma, (kompleksitas komputasi, atau kompleksitas Kolmogorov), adalah ide dasar baik dalam teori kompleksitas komputasi dan teori informasi algoritmik, dan memainkan peran penting dalam induksi formal.
Kompleksitas algoritme string biner didefinisikan sebagai program terpendek dan paling efisien yang dapat menghasilkan string. Meskipun ada jumlah program yang tidak terbatas yang dapat menghasilkan string tertentu, satu program atau grup program akan selalu menjadi yang terpendek. Tidak ada cara algoritmik untuk menemukan algoritme terpendek yang menghasilkan string tertentu; ini adalah salah satu hasil pertama dari teori kompleksitas komputasi. Meski begitu, kita bisa membuat tebakan yang cerdas. Hasil ini, (kompleksitas komputasi string), ternyata menjadi sangat penting untuk pembuktian yang berhubungan dengan komputabilitas.
Karena objek atau properti fisik apa pun pada prinsipnya dapat dideskripsikan hingga hampir habis oleh serangkaian bit, objek dan properti dapat dikatakan memiliki kompleksitas algoritmik juga. Faktanya, mengurangi kompleksitas objek dunia nyata ke program yang menghasilkan objek sebagai output, adalah salah satu cara untuk melihat perusahaan sains. Objek kompleks di sekitar kita cenderung berasal dari tiga proses pembangkit utama; kemunculan, evolusi, dan kecerdasan, dengan objek yang dihasilkan oleh masing-masing cenderung ke arah kompleksitas algoritmik yang lebih besar.
Kompleksitas komputasi adalah gagasan yang sering digunakan dalam ilmu komputer teoretis untuk menentukan kesulitan relatif komputasi solusi untuk kelas yang luas dari masalah matematika dan logika. Lebih dari 400 kelas kompleksitas ada, dan kelas tambahan terus ditemukan. Pertanyaan P = NP yang terkenal menyangkut sifat dua kelas kompleksitas ini. Kelas kompleksitas mencakup masalah yang jauh lebih sulit daripada apa pun yang mungkin dihadapi seseorang dalam matematika hingga kalkulus. Ada banyak masalah yang bisa dibayangkan dalam teori kompleksitas komputasi yang akan membutuhkan waktu yang hampir tak terbatas untuk diselesaikan.
Kompleksitas algoritma dan konsep terkait dikembangkan pada 1960-an oleh puluhan peneliti. Andrey Kolmogorov, Ray Solomonoff dan Gregory Chaitin memberikan kontribusi penting di akhir tahun 60-an dengan teori informasi algoritmik. Prinsip panjang pesan minimum, terkait erat dengan kompleksitas algoritmik, menyediakan banyak dasar inferensi statistik dan induktif dan pembelajaran mesin.