DAA - Kompleksitas Ruang

Dalam bab ini, kita akan membahas kompleksitas masalah komputasi sehubungan dengan jumlah ruang yang dibutuhkan algoritme.

Kompleksitas ruang berbagi banyak fitur kompleksitas waktu dan berfungsi sebagai cara lebih lanjut untuk mengklasifikasikan masalah menurut kesulitan komputasi mereka.

Apa itu Space Complexity?

Kompleksitas ruang adalah fungsi yang menjelaskan jumlah memori (ruang) yang diambil algoritme dalam hal jumlah input ke algoritme.

Kita sering membicarakannya extra memorydibutuhkan, tidak termasuk memori yang dibutuhkan untuk menyimpan input itu sendiri. Sekali lagi, kami menggunakan satuan alami (tapi panjang tetap) untuk mengukurnya.

Kita dapat menggunakan byte, tetapi lebih mudah digunakan, katakanlah, jumlah bilangan bulat yang digunakan, jumlah struktur berukuran tetap, dll.

Pada akhirnya, fungsi yang kita hasilkan akan tidak bergantung pada jumlah byte sebenarnya yang diperlukan untuk mewakili unit.

Kompleksitas ruang terkadang diabaikan karena ruang yang digunakan minimal dan / atau jelas, namun terkadang menjadi masalah yang sama pentingnya dengan kompleksitas waktu

Definisi

Membiarkan M menjadi deterministik Turing machine (TM)yang menghentikan semua input. Kompleksitas ruangM adalah fungsi $ f \ titik dua N \ kananarrow N $, di mana f(n) adalah jumlah maksimum sel tape dan M memindai input dengan panjang apa pun M. Jika kompleksitas ruangM adalah f(n), kita bisa bilang begitu M berjalan di luar angkasa f(n).

Kami memperkirakan kompleksitas ruang mesin Turing dengan menggunakan notasi asimtotik.

Misalkan $ f \ colon N \ rightarrow R ^ + $ menjadi sebuah fungsi. Kelas kompleksitas ruang dapat didefinisikan sebagai berikut -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE adalah kelas bahasa yang dapat didekripsi dalam ruang polinomial pada mesin Turing deterministik.

Dengan kata lain, PSPACE = U_k SPACE (n^k)

Teorema Savitch

Salah satu teorema paling awal yang terkait dengan kompleksitas ruang adalah teorema Savitch. Menurut teorema ini, mesin deterministik dapat mensimulasikan mesin non-deterministik dengan menggunakan sedikit ruang.

Untuk kompleksitas waktu, simulasi semacam itu tampaknya membutuhkan peningkatan waktu secara eksponensial. Untuk kompleksitas ruang, teorema ini menunjukkan bahwa setiap mesin Turing non deterministik yang digunakanf(n) ruang dapat diubah menjadi TM deterministik yang digunakan f²(n) ruang.

Karenanya, teorema Savitch menyatakan bahwa, untuk fungsi apa pun, $ f \ titik dua N \ rightarrow R ^ + $, di mana $ f (n) \ geqslant n $

NSPACE(f(n)) ⊆ SPACE(f(n))