Độ phức tạp không gian¶

Độ phức tạp không gian đo lường xu hướng tăng trưởng của không gian bộ nhớ mà một thuật toán chiếm dụng khi kích thước dữ liệu tăng lên. Khái niệm này rất giống với độ phức tạp thời gian, ngoại trừ việc "thời gian chạy" được thay thế bằng "không gian bộ nhớ chiếm dụng".

Không gian liên quan đến thuật toán¶

Không gian bộ nhớ mà thuật toán sử dụng trong quá trình thực thi chủ yếu bao gồm các loại sau đây.

Không gian đầu vào: Được dùng để lưu trữ dữ liệu đầu vào của thuật toán.
Không gian tạm thời: Được dùng để lưu trữ các biến, đối tượng, ngữ cảnh hàm và dữ liệu khác trong quá trình thuật toán thực thi.
Không gian đầu ra: Được dùng để lưu trữ dữ liệu đầu ra của thuật toán.

Thông thường, phạm vi thống kê độ phức tạp không gian là "không gian tạm thời" cộng với "không gian đầu ra".

Không gian tạm thời có thể được chia tiếp thành ba phần:

Dữ liệu tạm thời: Dùng để lưu trữ các hằng số, biến số, đối tượng, v.v., trong quá trình thuật toán thực thi.
Không gian khung ngăn xếp (stack frame space): Dùng để lưu trữ dữ liệu ngữ cảnh của các hàm được gọi. Hệ thống tạo một khung ngăn xếp (stack frame) ở trên cùng của ngăn xếp (stack) mỗi khi một hàm được gọi, và không gian khung ngăn xếp này sẽ được giải phóng sau khi hàm trả về.
Không gian lệnh: Dùng để lưu trữ các lệnh chương trình đã được biên dịch, phần này thường được bỏ qua trong các thống kê thực tế.

Khi phân tích độ phức tạp không gian của một chương trình, chúng ta thường xem xét ba phần: dữ liệu tạm thời, không gian khung ngăn xếp và dữ liệu đầu ra, như được minh họa trong hình bên dưới.

Mã nguồn liên quan như sau:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

class Node:
    """Lớp"""
    def __init__(self, x: int):
        self.val: int = x              # Giá trị nút
        self.next: Node | None = None  # Tham chiếu đến nút tiếp theo

def function() -> int:
    """Hàm"""
    # Thực hiện một số thao tác...
    return 0

def algorithm(n) -> int:  # Dữ liệu đầu vào
    A = 0                 # Dữ liệu tạm thời (hằng số, thường biểu diễn bằng chữ in hoa)
    b = 0                 # Dữ liệu tạm thời (biến số)
    node = Node(0)        # Dữ liệu tạm thời (đối tượng)
    c = function()        # Không gian khung ngăn xếp (gọi hàm)
    return A + b + c      # Dữ liệu đầu ra

/* Cấu trúc */
struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(nullptr) {}
};

/* Hàm */
int func() {
    // Thực hiện một số thao tác...
    return 0;
}

int algorithm(int n) {        // Dữ liệu đầu vào
    const int a = 0;          // Dữ liệu tạm thời (hằng số)
    int b = 0;                // Dữ liệu tạm thời (biến số)
    Node* node = new Node(0); // Dữ liệu tạm thời (đối tượng)
    int c = func();           // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;         // Dữ liệu đầu ra
}

/* Lớp */
class Node {
    int val;
    Node next;
    Node(int x) { val = x; }
}

/* Hàm */
int function() {
    // Thực hiện một số thao tác...
    return 0;
}

int algorithm(int n) {        // Dữ liệu đầu vào
    final int a = 0;          // Dữ liệu tạm thời (hằng số)
    int b = 0;                // Dữ liệu tạm thời (biến số)
    Node node = new Node(0);  // Dữ liệu tạm thời (đối tượng)
    int c = function();       // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;         // Dữ liệu đầu ra
}

/* Lớp */
class Node(int x) {
    int val = x;
    Node next;
}

/* Hàm */
int Function() {
    // Thực hiện một số thao tác...
    return 0;
}

int Algorithm(int n) {        // Dữ liệu đầu vào
    const int a = 0;          // Dữ liệu tạm thời (hằng số)
    int b = 0;                // Dữ liệu tạm thời (biến số)
    Node node = new(0);       // Dữ liệu tạm thời (đối tượng)
    int c = Function();       // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;         // Dữ liệu đầu ra
}

/* Cấu trúc */
type node struct {
    val  int
    next *node
}

/* Tạo cấu trúc nút */
func newNode(val int) *node {
    return &node{val: val}
}

/* Hàm */
func function() int {
    // Thực hiện một số thao tác...
    return 0
}

func algorithm(n int) int { // Dữ liệu đầu vào
    const a = 0             // Dữ liệu tạm thời (hằng số)
    b := 0                  // Dữ liệu tạm thời (biến số)
    newNode(0)              // Dữ liệu tạm thời (đối tượng)
    c := function()         // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c        // Dữ liệu đầu ra
}

/* Lớp */
class Node {
    var val: Int
    var next: Node?

    init(x: Int) {
        val = x
    }
}

/* Hàm */
func function() -> Int {
    // Thực hiện một số thao tác...
    return 0
}

func algorithm(n: Int) -> Int { // Dữ liệu đầu vào
    let a = 0             // Dữ liệu tạm thời (hằng số)
    var b = 0             // Dữ liệu tạm thời (biến số)
    let node = Node(x: 0) // Dữ liệu tạm thời (đối tượng)
    let c = function()    // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c      // Dữ liệu đầu ra
}

/* Lớp */
class Node {
    val;
    next;
    constructor(val) {
        this.val = val === undefined ? 0 : val; // Giá trị nút
        this.next = null;                       // Tham chiếu đến nút tiếp theo
    }
}

/* Hàm */
function constFunc() {
    // Thực hiện một số thao tác...
    return 0;
}

function algorithm(n) {       // Dữ liệu đầu vào
    const a = 0;              // Dữ liệu tạm thời (hằng số)
    let b = 0;                // Dữ liệu tạm thời (biến số)
    const node = new Node(0); // Dữ liệu tạm thời (đối tượng)
    const c = constFunc();    // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;         // Dữ liệu đầu ra
}

/* Lớp */
class Node {
    val: number;
    next: Node | null;
    constructor(val?: number) {
        this.val = val === undefined ? 0 : val; // Giá trị nút
        this.next = null;                       // Tham chiếu đến nút tiếp theo
    }
}

/* Hàm */
function constFunc(): number {
    // Thực hiện một số thao tác...
    return 0;
}

function algorithm(n: number): number { // Dữ liệu đầu vào
    const a = 0;                        // Dữ liệu tạm thời (hằng số)
    let b = 0;                          // Dữ liệu tạm thời (biến số)
    const node = new Node(0);           // Dữ liệu tạm thời (đối tượng)
    const c = constFunc();              // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;                   // Dữ liệu đầu ra
}

/* Lớp */
class Node {
  int val;
  Node next;
  Node(this.val, [this.next]);
}

/* Hàm */
int function() {
  // Thực hiện một số thao tác...
  return 0;
}

int algorithm(int n) {  // Dữ liệu đầu vào
  const int a = 0;      // Dữ liệu tạm thời (hằng số)
  int b = 0;            // Dữ liệu tạm thời (biến số)
  Node node = Node(0);  // Dữ liệu tạm thời (đối tượng)
  int c = function();   // Không gian khung ngăn xếp (gọi hàm)
  return a + b + c;     // Dữ liệu đầu ra
}

use std::rc::Rc;
use std::cell::RefCell;

/* Cấu trúc */
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

/* Tạo cấu trúc Node */
impl Node {
    fn new(val: i32) -> Self {
        Self { val: val, next: None }
    }
}

/* Hàm */
fn function() -> i32 {
    // Thực hiện một số thao tác...
    return 0;
}

fn algorithm(n: i32) -> i32 {       // Dữ liệu đầu vào
    const a: i32 = 0;               // Dữ liệu tạm thời (hằng số)
    let mut b = 0;                  // Dữ liệu tạm thời (biến số)
    let node = Node::new(0);        // Dữ liệu tạm thời (đối tượng)
    let c = function();             // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;               // Dữ liệu đầu ra
}

/* Hàm */
int func() {
    // Thực hiện một số thao tác...
    return 0;
}

int algorithm(int n) { // Dữ liệu đầu vào
    const int a = 0;   // Dữ liệu tạm thời (hằng số)
    int b = 0;         // Dữ liệu tạm thời (biến số)
    int c = func();    // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c;  // Dữ liệu đầu ra
}

/* Lớp */
class Node(var _val: Int) {
    var next: Node? = null
}

/* Hàm */
fun function(): Int {
    // Thực hiện một số thao tác...
    return 0
}

fun algorithm(n: Int): Int { // Dữ liệu đầu vào
    val a = 0                // Dữ liệu tạm thời (hằng số)
    var b = 0                // Dữ liệu tạm thời (biến số)
    val node = Node(0)       // Dữ liệu tạm thời (đối tượng)
    val c = function()       // Không gian khung ngăn xếp (gọi hàm)
    return a + b + c         // Dữ liệu đầu ra
}

### Lớp ###
class Node
    attr_accessor :val      # Giá trị nút
    attr_accessor :next     # Tham chiếu đến nút tiếp theo

    def initialize(x)
        @val = x
    end
end

### Hàm ###
def function
    # Thực hiện một số thao tác...
    0
end

### Thuật toán ###
def algorithm(n)        # Dữ liệu đầu vào
    a = 0               # Dữ liệu tạm thời (hằng số)
    b = 0               # Dữ liệu tạm thời (biến số)
    node = Node.new(0)  # Dữ liệu tạm thời (đối tượng)
    c = function        # Không gian khung ngăn xếp (gọi hàm)
    a + b + c           # Dữ liệu đầu ra
end

Phương pháp suy dẫn¶

Phương pháp tính toán độ phức tạp không gian về cơ bản giống như độ phức tạp thời gian, ngoại trừ việc đối tượng đo lường thay đổi từ "số lượng thao tác" thành "lượng không gian sử dụng".

Khác với độ phức tạp thời gian, chúng ta thường chỉ quan tâm đến độ phức tạp không gian trong trường hợp xấu nhất. Điều này là do không gian bộ nhớ là một yêu cầu phần cứng bắt buộc, và chúng ta phải đảm bảo rằng có đủ dung lượng bộ nhớ được cấp phát cho mọi dữ liệu đầu vào.

Hãy quan sát đoạn mã sau. Ở đây, "xấu nhất" trong độ phức tạp không gian trong trường hợp xấu nhất có hai ý nghĩa:

Dựa trên dữ liệu đầu vào xấu nhất: Khi \(n < 10\), độ phức tạp không gian là \(O(1)\); nhưng khi \(n > 10\), mảng nums được khởi tạo sẽ chiếm không gian \(O(n)\), do đó độ phức tạp không gian trong trường hợp xấu nhất là \(O(n)\).
Dựa trên bộ nhớ đỉnh (peak memory) trong quá trình thực thi thuật toán: Ví dụ, trước khi thực hiện dòng cuối cùng, chương trình chiếm không gian \(O(1)\); khi khởi tạo mảng nums, chương trình chiếm không gian \(O(n)\), vì vậy độ phức tạp không gian trong trường hợp xấu nhất là \(O(n)\).

Trong các hàm đệ quy, việc tính toán không gian khung ngăn xếp là rất cần thiết. Hãy quan sát đoạn mã sau:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

def function() -> int:
    # Thực hiện một số thao tác
    return 0

def loop(n: int):
    """Vòng lặp có độ phức tạp không gian là O(1)"""
    for _ in range(n):
        function()

def recur(n: int):
    """Đệ quy có độ phức tạp không gian là O(n)"""
    if n == 1:
        return
    return recur(n - 1)

int func() {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        func();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
void recur(int n) {
    if (n == 1) return;
    recur(n - 1);
}

int function() {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        function();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
void recur(int n) {
    if (n == 1) return;
    recur(n - 1);
}

int Function() {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
void Loop(int n) {
    for (int i = 0; i < n; i++) {
        Function();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
int Recur(int n) {
    if (n == 1) return 1;
    return Recur(n - 1);
}

func function() int {
    // Thực hiện một số thao tác
    return 0
}

/* Vòng lặp có độ phức tạp không gian là O(1) */
func loop(n int) {
    for i := 0; i < n; i++ {
        function()
    }
}

/* Đệ quy có độ phức tạp không gian là O(n) */
func recur(n int) {
    if n == 1 {
        return
    }
    recur(n - 1)
}

@discardableResult
func function() -> Int {
    // Thực hiện một số thao tác
    return 0
}

/* Vòng lặp có độ phức tạp không gian là O(1) */
func loop(n: Int) {
    for _ in 0 ..< n {
        function()
    }
}

/* Đệ quy có độ phức tạp không gian là O(n) */
func recur(n: Int) {
    if n == 1 {
        return
    }
    recur(n: n - 1)
}

function constFunc() {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
function loop(n) {
    for (let i = 0; i < n; i++) {
        constFunc();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
function recur(n) {
    if (n === 1) return;
    return recur(n - 1);
}

function constFunc(): number {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
function loop(n: number): void {
    for (let i = 0; i < n; i++) {
        constFunc();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
function recur(n: number): void {
    if (n === 1) return;
    return recur(n - 1);
}

int function() {
  // Thực hiện một số thao tác
  return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
void loop(int n) {
  for (int i = 0; i < n; i++) {
    function();
  }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
void recur(int n) {
  if (n == 1) return;
  recur(n - 1);
}

fn function() -> i32 {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
fn loop(n: i32) {
    for i in 0..n {
        function();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
fn recur(n: i32) {
    if n == 1 {
        return;
    }
    recur(n - 1);
}

int func() {
    // Thực hiện một số thao tác
    return 0;
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        func();
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
void recur(int n) {
    if (n == 1) return;
    recur(n - 1);
}

fun function(): Int {
    // Thực hiện một số thao tác
    return 0
}
/* Vòng lặp có độ phức tạp không gian là O(1) */
fun loop(n: Int) {
    for (i in 0..<n) {
        function()
    }
}
/* Đệ quy có độ phức tạp không gian là O(n) */
fun recur(n: Int) {
    if (n == 1) return
    return recur(n - 1)
}

def function
    # Thực hiện một số thao tác
    0
end

### Vòng lặp có độ phức tạp không gian là O(1) ###
def loop(n)
    (0...n).each { function }
end

### Đệ quy có độ phức tạp không gian là O(n) ###
def recur(n)
    return if n == 1
    recur(n - 1)
end

Độ phức tạp thời gian của cả hai hàm loop() và recur() đều là \(O(n)\), nhưng độ phức tạp không gian của chúng lại khác nhau.

Hàm loop() gọi hàm function() \(n\) lần trong một vòng lặp. Trong mỗi lần lặp, hàm function() trả về và giải phóng không gian khung ngăn xếp của nó, vì vậy độ phức tạp không gian duy trì ở mức \(O(1)\).
Hàm đệ quy recur() có \(n\) lượt gọi recur() chưa trả về tồn tại đồng thời trong suốt quá trình thực thi, từ đó chiếm dụng không gian khung ngăn xếp là \(O(n)\).

Các dạng thường gặp¶

Giả sử kích thước dữ liệu đầu vào là \(n\). Hình bên dưới thể hiện các loại độ phức tạp không gian phổ biến (được sắp xếp từ thấp đến cao).

\[ \begin{aligned} & O(1) < O(\log n) < O(n) < O(n^2) < O(2^n) \newline & \text{Bậc hằng số} < \text{Bậc lôgarit} < \text{Bậc tuyến tính} < \text{Bậc bình phương} < \text{Bậc mũ} \end{aligned} \]

Bậc hằng số \(O(1)\)¶

Bậc hằng số thường gặp ở các hằng số, biến số và đối tượng có số lượng không phụ thuộc vào kích thước dữ liệu đầu vào \(n\).

Cần lưu ý rằng bộ nhớ bị chiếm dụng do khởi tạo biến hoặc gọi hàm trong một vòng lặp sẽ được giải phóng khi bước vào lần lặp tiếp theo, do đó nó không tích lũy không gian, và độ phức tạp không gian vẫn duy trì ở mức \(O(1)\):

[file]{space_complexity}-[class]{}-[func]{constant}

Bậc tuyến tính \(O(n)\)¶

Bậc tuyến tính thường gặp ở các mảng, danh sách liên kết, ngăn xếp, hàng đợi, v.v., nơi số lượng phần tử tỉ lệ thuận với \(n\):

[file]{space_complexity}-[class]{}-[func]{linear}

Như được minh họa trong hình bên dưới, độ sâu đệ quy của hàm này là \(n\), nghĩa là có \(n\) lượt gọi hàm linear_recur() chưa trả về kết quả tồn tại đồng thời, sử dụng không gian khung ngăn xếp là \(O(n)\):

[file]{space_complexity}-[class]{}-[func]{linear_recur}

Bậc bình phương \(O(n^2)\)¶

Bậc bình phương thường gặp ở các ma trận và đồ thị, nơi số lượng phần tử có mối quan hệ bậc hai với \(n\):

[file]{space_complexity}-[class]{}-[func]{quadratic}

Như được minh họa trong hình bên dưới, độ sâu đệ quy của hàm này là \(n\), và một mảng được khởi tạo trong mỗi lần gọi hàm đệ quy với các độ dài lần lượt là \(n\), \(n-1\), \(\dots\), \(2\), \(1\), với độ dài trung bình là \(n / 2\), do đó chiếm dụng tổng cộng \(O(n^2)\) không gian:

[file]{space_complexity}-[class]{}-[func]{quadratic_recur}

Bậc mũ \(O(2^n)\)¶

Bậc mũ thường gặp ở các cây nhị phân. Hãy quan sát hình bên dưới: một "cây nhị phân đầy đủ" có \(n\) tầng sẽ có \(2^n - 1\) nút, chiếm dụng không gian \(O(2^n)\):

[file]{space_complexity}-[class]{}-[func]{build_tree}

Bậc lôgarit \(O(\log n)\)¶

Bậc lôgarit thường gặp trong các thuật toán chia để trị. Ví dụ, sắp xếp trộn (merge sort): cho một mảng đầu vào có độ dài là \(n\), mỗi lượt gọi đệ quy sẽ chia mảng làm đôi từ điểm giữa, tạo thành một cây đệ quy có chiều cao là \(\log n\), sử dụng \(O(\log n)\) không gian khung ngăn xếp.

Một ví dụ khác là chuyển đổi một số thành chuỗi ký tự. Cho một số nguyên dương \(n\), nó có \(\lfloor \log_{10} n \rfloor + 1\) chữ số, tức là độ dài chuỗi tương ứng là \(\lfloor \log_{10} n \rfloor + 1\), do đó độ phức tạp không gian là \(O(\log_{10} n + 1) = O(\log n)\).

Đánh đổi thời gian lấy không gian¶

Lý tưởng nhất, chúng ta hy vọng cả độ phức tạp thời gian và độ phức tạp không gian của một thuật toán đều đạt mức tối ưu. Tuy nhiên trên thực tế, việc tối ưu hóa đồng thời cả độ phức tạp thời gian và độ phức tạp không gian thường rất khó khăn.

Việc giảm độ phức tạp thời gian thường phải trả giá bằng việc tăng độ phức tạp không gian và ngược lại. Việc hy sinh không gian bộ nhớ để cải thiện tốc độ chạy của thuật toán được gọi là "đổi không gian lấy thời gian"; điều ngược lại được gọi là "đổi thời gian lấy không gian".

Việc lựa chọn phương án nào phụ thuộc vào khía cạnh nào mà chúng ta coi trọng hơn. Trong hầu hết các trường hợp, thời gian quý giá hơn không gian bộ nhớ, vì vậy "đổi không gian lấy thời gian" thường là chiến lược phổ biến hơn. Tất nhiên, khi lượng dữ liệu cực kỳ lớn, việc kiểm soát độ phức tạp không gian cũng trở nên rất quan trọng.