DAA - ความซับซ้อนของอวกาศ

ในบทนี้เราจะพูดถึงความซับซ้อนของปัญหาด้านการคำนวณเกี่ยวกับจำนวนพื้นที่ที่อัลกอริทึมต้องการ

ความซับซ้อนของอวกาศแบ่งปันคุณลักษณะต่างๆของความซับซ้อนของเวลาและทำหน้าที่เป็นวิธีการเพิ่มเติมในการจำแนกปัญหาตามความยากลำบากในการคำนวณ

Space Complexity คืออะไร?

ความซับซ้อนของพื้นที่เป็นฟังก์ชันที่อธิบายจำนวนหน่วยความจำ (ช่องว่าง) ที่อัลกอริทึมใช้ในแง่ของจำนวนอินพุตไปยังอัลกอริทึม

เรามักจะพูดถึง extra memoryจำเป็นโดยไม่นับหน่วยความจำที่จำเป็นในการจัดเก็บอินพุตเอง อีกครั้งเราใช้หน่วยธรรมชาติ (แต่มีความยาวคงที่) เพื่อวัดสิ่งนี้

เราสามารถใช้ไบต์ได้ แต่ใช้ง่ายกว่าเช่นจำนวนเต็มที่ใช้จำนวนโครงสร้างขนาดคงที่เป็นต้น

ในท้ายที่สุดฟังก์ชันที่เราสร้างขึ้นจะไม่ขึ้นอยู่กับจำนวนไบต์จริงที่จำเป็นในการแสดงหน่วย

ความซับซ้อนของพื้นที่บางครั้งถูกละเลยเนื่องจากพื้นที่ที่ใช้มีน้อยและ / หรือชัดเจน แต่บางครั้งก็กลายเป็นปัญหาที่สำคัญพอ ๆ กับความซับซ้อนของเวลา

คำจำกัดความ

ปล่อย M เป็นปัจจัยกำหนด Turing machine (TM)ที่หยุดอินพุตทั้งหมด ความซับซ้อนของพื้นที่M คือฟังก์ชัน $ f \ colon N \ rightarrow N $ โดยที่ f(n) คือจำนวนเซลล์สูงสุดของเทปและ M สแกนอินพุตของความยาวใด ๆ M. ถ้าความซับซ้อนของช่องว่างของM คือ f(n)เราสามารถพูดได้ว่า M วิ่งในอวกาศ f(n).

เราประเมินความซับซ้อนของพื้นที่ของเครื่องทัวริงโดยใช้สัญกรณ์แบบไม่แสดงอาการ

ให้ $ f \ colon N \ rightarrow R ^ + $ เป็นฟังก์ชัน คลาสความซับซ้อนของพื้นที่สามารถกำหนดได้ดังนี้ -

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 เป็นคลาสของภาษาที่สามารถตัดสินใจได้ในปริภูมิพหุนามบนเครื่องทัวริงที่กำหนดได้

กล่าวอีกนัยหนึ่ง PSPACE = U_k SPACE (n^k)

ทฤษฎีบทของ Savitch

หนึ่งในทฤษฎีบทแรกสุดที่เกี่ยวข้องกับความซับซ้อนของอวกาศคือทฤษฎีบทของซาวิทช์ ตามทฤษฎีบทนี้เครื่องจักรดีเทอร์มินิสติกสามารถจำลองเครื่องจักรที่ไม่ได้กำหนดได้โดยใช้พื้นที่เพียงเล็กน้อย

สำหรับความซับซ้อนของเวลาการจำลองแบบนี้ดูเหมือนจะต้องใช้เวลาเพิ่มขึ้นแบบทวีคูณ สำหรับความซับซ้อนของอวกาศทฤษฎีบทนี้แสดงให้เห็นว่าเครื่องจักรทัวริงที่ไม่ได้กำหนดปัจจัยใด ๆ ที่ใช้f(n) ช่องว่างสามารถแปลงเป็น TM แบบกำหนดที่ใช้ f²(n) พื้นที่

ดังนั้นทฤษฎีบทของ Savitch จึงระบุว่าสำหรับฟังก์ชันใด ๆ $ f \ colon N \ rightarrow R ^ + $ โดยที่ $ f (n) \ geqslant n $

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