DAA - Sự phức tạp về không gian

Trong chương này, chúng ta sẽ thảo luận về độ phức tạp của các bài toán tính toán liên quan đến lượng không gian mà một thuật toán yêu cầu.

Độ phức tạp về không gian chia sẻ nhiều đặc điểm của độ phức tạp về thời gian và là một cách khác để phân loại các vấn đề theo độ khó tính toán của chúng.

Không gian phức tạp là gì?

Độ phức tạp không gian là một hàm mô tả số lượng bộ nhớ (không gian) mà một thuật toán sử dụng về số lượng đầu vào cho thuật toán.

Chúng tôi thường nói về extra memorycần thiết, không tính bộ nhớ cần thiết để lưu trữ dữ liệu đầu vào. Một lần nữa, chúng tôi sử dụng các đơn vị tự nhiên (nhưng độ dài cố định) để đo điều này.

Chúng ta có thể sử dụng byte, nhưng dễ sử dụng hơn, chẳng hạn như số lượng số nguyên được sử dụng, số lượng cấu trúc có kích thước cố định, v.v.

Cuối cùng, hàm mà chúng ta nghĩ ra sẽ độc lập với số byte thực tế cần thiết để đại diện cho đơn vị.

Độ phức tạp về không gian đôi khi bị bỏ qua vì không gian được sử dụng là tối thiểu và / hoặc hiển nhiên, tuy nhiên, đôi khi nó trở thành vấn đề quan trọng như độ phức tạp về thời gian

Định nghĩa

Để cho M là một người xác định Turing machine (TM)điều đó tạm dừng trên tất cả các đầu vào. Không gian phức tạp củaM là hàm $ f \ dấu hai chấm N \ rightarrow N $, trong đó f(n) là số ô tối đa của băng và M quét mọi đầu vào có độ dài M. Nếu không gian phức tạp củaM Là f(n), chúng ta có thể nói về điều đó M chạy trong không gian f(n).

Chúng tôi ước tính độ phức tạp không gian của máy Turing bằng cách sử dụng ký hiệu tiệm cận.

Gọi $ f \ dấu hai chấm N \ rightarrow R ^ + $ là một hàm. Các lớp độ phức tạp không gian có thể được định nghĩa như sau:

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 là lớp ngôn ngữ có thể giải mã trong không gian đa thức trên máy Turing xác định.

Nói cách khác, PSPACE = U_k SPACE (n^k)

Định lý Savitch

Một trong những định lý sớm nhất liên quan đến độ phức tạp của không gian là định lý Savitch. Theo định lý này, một máy xác định có thể mô phỏng máy không xác định bằng cách sử dụng một lượng nhỏ không gian.

Đối với độ phức tạp về thời gian, một mô phỏng như vậy dường như yêu cầu thời gian tăng theo cấp số nhân. Đối với độ phức tạp của không gian, định lý này cho thấy rằng bất kỳ máy Turing không xác định nào sử dụngf(n) không gian có thể được chuyển đổi thành một TM xác định sử dụng f²(n) không gian.

Do đó, định lý Savitch nói rằng, đối với bất kỳ hàm nào, $ f \ dấu hai chấm N \ rightarrow R ^ + $, trong đó $ f (n) \ geqslant n $

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