Kompleksitas waktu seringkali sebenarnya kurang penting daripada kompleksitas ruang , meskipun jelas keduanya penting. Namun terkadang kompleksitas waktu lebih penting . Ruang Anda tetap untuk perangkat keras apa pun. Jika Anda tidak memiliki cukup, Anda tidak dapat menjalankan algoritme.
Dalam hal ini, apa perbedaan antara kompleksitas waktu dan ruang?
Kompleksitas waktu berkaitan dengan mencari tahu bagaimana waktu komputasi dari suatu algoritma berubah dengan perubahan ukuran input. Di sisi lain, kompleksitas ruang berkaitan dengan mencari tahu berapa banyak ruang (ekstra) yang dibutuhkan oleh algoritma dengan perubahan ukuran input.
Kedua, apakah kompleksitas ruang termasuk input? Kompleksitas Ruang dari suatu algoritma adalah total ruang yang diambil oleh algoritma sehubungan dengan ukuran input . Kompleksitas ruang mencakup ruang bantu dan ruang yang digunakan oleh input .
Sehubungan dengan ini, mengapa kompleksitas ruang itu penting?
Kompleksitas ruang adalah fungsi yang menggambarkan jumlah memori ( ruang ) yang dibutuhkan suatu algoritma dalam hal jumlah input ke algoritma. Kompleksitas ruang terkadang diabaikan karena ruang yang digunakan minimal dan/atau jelas, tetapi terkadang menjadi masalah yang sama pentingnya dengan waktu.
Apa kompleksitas waktu untuk loop?
Loop dieksekusi N kali , jadi urutan pernyataan juga dieksekusi N kali . Karena kita menganggap pernyataannya adalah O(1), total waktu untuk perulangan for adalah N * O(1), yang merupakan O(N) secara keseluruhan. Loop luar mengeksekusi N kali . Setiap kali loop luar dieksekusi, loop dalam dieksekusi M kali .