Độ phức tạp bộ nhớ (Space Complexity)

Bài viết này giúp bạn hiểu cách phân tích độ phức tạp bộ nhớ thông qua các ví dụ cụ thể với phân tích từng bước.

Space Complexity là gì?

Space Complexity đo lường lượng bộ nhớ bổ sung mà thuật toán cần sử dụng, không tính input.

💡

Space Complexity chỉ tính bộ nhớ phụ trợ (auxiliary space) - bộ nhớ mà thuật toán tạo thêm, không bao gồm input!

Các mức độ phổ biến

Space	Ý nghĩa	Ví dụ
O(1)	Constant - cố định	Biến đếm, swap
O(n)	Linear - tỷ lệ với n	Tạo mảng mới kích thước n
O(n²)	Quadratic	Ma trận 2D n×n
O(log n)	Logarithmic	Đệ quy chia đôi (call stack)

Ví dụ 1: O(1) Space - In-place Operations

Bài toán

Đảo ngược mảng tại chỗ (in-place).

Python


def reverse_inplace(arr):
    left = 0                  # 1 biến int
    right = len(arr) - 1      # 1 biến int
    
    while left < right:
        # Swap không cần biến tạm (Python)
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    
    return arr

Kotlin


fun reverseInplace(arr: MutableList<Int>): List<Int> {
    var left = 0              // 1 biến int
    var right = arr.size - 1  // 1 biến int
    
    while (left < right) {
        val temp = arr[left]  // 1 biến tạm
        arr[left] = arr[right]
        arr[right] = temp
        left++; right--
    }
    return arr
}

Dart


List<int> reverseInplace(List<int> arr) {
  int left = 0;               // 1 biến int
  int right = arr.length - 1; // 1 biến int
  
  while (left < right) {
    int temp = arr[left];     // 1 biến tạm
    arr[left] = arr[right];
    arr[right] = temp;
    left++; right--;
  }
  return arr;
}

Swift


func reverseInplace(_ arr: inout [Int]) {
    var left = 0              // 1 biến int
    var right = arr.count - 1 // 1 biến int
    
    while left < right {
        arr.swapAt(left, right) // Built-in swap
        left += 1; right -= 1
    }
}

Java


void reverseInplace(int[] arr) {
    int left = 0;             // 1 biến int
    int right = arr.length - 1; // 1 biến int
    
    while (left < right) {
        int temp = arr[left]; // 1 biến tạm
        arr[left] = arr[right];
        arr[right] = temp;
        left++; right--;
    }
}

Phân tích bộ nhớ:

left: 4 bytes (int)
right: 4 bytes (int)
temp: 4 bytes (int)

Tổng: 12 bytes - không phụ thuộc n → O(1)

💡

Dù mảng có 10 hay 10 triệu phần tử, ta vẫn chỉ dùng 3 biến!

Ví dụ 2: O(n) Space - Tạo mảng mới

Bài toán

Đảo ngược mảng bằng cách tạo mảng mới.

Python


def reverse_copy(arr):
    n = len(arr)
    result = []           # Mảng mới rỗng
    
    for i in range(n - 1, -1, -1):
        result.append(arr[i])  # Thêm n phần tử
    
    return result
    # result chứa n phần tử → O(n) space

Kotlin


fun reverseCopy(arr: List<Int>): List<Int> {
    val result = mutableListOf<Int>()  // List mới rỗng
    
    for (i in arr.size - 1 downTo 0) {
        result.add(arr[i])  // Thêm n phần tử
    }
    
    return result
    // result chứa n phần tử → O(n) space
}

Dart


List<int> reverseCopy(List<int> arr) {
  List<int> result = [];      // List mới rỗng
  
  for (int i = arr.length - 1; i >= 0; i--) {
    result.add(arr[i]);       // Thêm n phần tử
  }
  
  return result;
  // result chứa n phần tử → O(n) space
}

Swift


func reverseCopy(_ arr: [Int]) -> [Int] {
    var result = [Int]()      // Array mới rỗng
    
    for i in stride(from: arr.count - 1, through: 0, by: -1) {
        result.append(arr[i]) // Thêm n phần tử
    }
    
    return result
    // result chứa n phần tử → O(n) space
}

Java


int[] reverseCopy(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];  // Mảng mới kích thước n
    
    for (int i = 0; i < n; i++) {
        result[i] = arr[n - 1 - i];
    }
    
    return result;
    // result chứa n phần tử → O(n) space
}

Phân tích bộ nhớ:

n: 4 bytes (int)
result: n × 4 bytes (n số int)
i: 4 bytes (int)

Tổng: 4 + 4n + 4 = 4n + 8 bytes → O(n)

Ví dụ 3: So sánh O(1) vs O(n)

Bài toán

Tìm tất cả các cặp có tổng bằng target.

Cách 1: Brute Force - O(1) Space

Python


def find_pairs_brute(arr, target):
    pairs = []                    # Chỉ lưu kết quả
    n = len(arr)
    
    for i in range(n):            # Không tạo cấu trúc phụ
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                pairs.append((arr[i], arr[j]))
    
    return pairs
# Space phụ trợ: O(1) (không tính output)

Kotlin


fun findPairsBrute(arr: List<Int>, target: Int): List<Pair<Int, Int>> {
    val pairs = mutableListOf<Pair<Int, Int>>()
    val n = arr.size
    
    for (i in 0 until n) {
        for (j in i + 1 until n) {
            if (arr[i] + arr[j] == target) {
                pairs.add(Pair(arr[i], arr[j]))
            }
        }
    }
    return pairs
}
// Space phụ trợ: O(1)

Dart


List<List<int>> findPairsBrute(List<int> arr, int target) {
  List<List<int>> pairs = [];
  int n = arr.length;
  
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (arr[i] + arr[j] == target) {
        pairs.add([arr[i], arr[j]]);
      }
    }
  }
  return pairs;
}
// Space phụ trợ: O(1)

Swift


func findPairsBrute(_ arr: [Int], _ target: Int) -> [(Int, Int)] {
    var pairs = [(Int, Int)]()
    let n = arr.count
    
    for i in 0..<n {
        for j in (i + 1)..<n {
            if arr[i] + arr[j] == target {
                pairs.append((arr[i], arr[j]))
            }
        }
    }
    return pairs
}
// Space phụ trợ: O(1)

Java


List<int[]> findPairsBrute(int[] arr, int target) {
    List<int[]> pairs = new ArrayList<>();
    int n = arr.length;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                pairs.add(new int[]{arr[i], arr[j]});
            }
        }
    }
    return pairs;
}
// Space phụ trợ: O(1)

Phân tích:

Chỉ dùng biến i, j, n
Không tạo cấu trúc dữ liệu phụ

Time: O(n²) | Space: O(1)

Cách 2: Hash Set - O(n) Space

Python


def find_pairs_hash(arr, target):
    pairs = []
    seen = set()          # Set chứa tối đa n phần tử
    
    for num in arr:
        complement = target - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)     # Mỗi phần tử thêm 1 lần
    
    return pairs
# Space phụ trợ: O(n) cho seen

Kotlin


fun findPairsHash(arr: List<Int>, target: Int): List<Pair<Int, Int>> {
    val pairs = mutableListOf<Pair<Int, Int>>()
    val seen = mutableSetOf<Int>()  // Set chứa tối đa n phần tử
    
    for (num in arr) {
        val complement = target - num
        if (complement in seen) {
            pairs.add(Pair(complement, num))
        }
        seen.add(num)
    }
    return pairs
}
// Space phụ trợ: O(n)

Dart


List<List<int>> findPairsHash(List<int> arr, int target) {
  List<List<int>> pairs = [];
  Set<int> seen = {};         // Set chứa tối đa n phần tử
  
  for (int num in arr) {
    int complement = target - num;
    if (seen.contains(complement)) {
      pairs.add([complement, num]);
    }
    seen.add(num);
  }
  return pairs;
}
// Space phụ trợ: O(n)

Swift


func findPairsHash(_ arr: [Int], _ target: Int) -> [(Int, Int)] {
    var pairs = [(Int, Int)]()
    var seen = Set<Int>()     // Set chứa tối đa n phần tử
    
    for num in arr {
        let complement = target - num
        if seen.contains(complement) {
            pairs.append((complement, num))
        }
        seen.insert(num)
    }
    return pairs
}
// Space phụ trợ: O(n)

Java


List<int[]> findPairsHash(int[] arr, int target) {
    List<int[]> pairs = new ArrayList<>();
    Set<Integer> seen = new HashSet<>();  // Set chứa tối đa n phần tử
    
    for (int num : arr) {
        int complement = target - num;
        if (seen.contains(complement)) {
            pairs.add(new int[]{complement, num});
        }
        seen.add(num);
    }
    return pairs;
}
// Space phụ trợ: O(n)

Phân tích:

seen: chứa tối đa n phần tử
Mỗi phần tử: ~4-8 bytes

Time: O(n) | Space: O(n)

⚠️

Space-Time Tradeoff: Cách 2 nhanh hơn (O(n) vs O(n²)) nhưng tốn thêm O(n) bộ nhớ!

Ví dụ 4: O(log n) Space - Đệ quy

Bài toán

Binary Search với đệ quy.

Python


def binary_search_recursive(arr, target, left, right):
    # Mỗi lần gọi đệ quy = 1 frame trên call stack
    
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
 
# Gọi: binary_search_recursive(arr, target, 0, len(arr) - 1)

Kotlin


fun binarySearchRecursive(arr: List<Int>, target: Int, left: Int, right: Int): Int {
    // Mỗi lần gọi đệ quy = 1 frame trên call stack
    
    if (left > right) return -1
    
    val mid = (left + right) / 2
    
    return when {
        arr[mid] == target -> mid
        arr[mid] < target -> binarySearchRecursive(arr, target, mid + 1, right)
        else -> binarySearchRecursive(arr, target, left, mid - 1)
    }
}

Dart


int binarySearchRecursive(List<int> arr, int target, int left, int right) {
  // Mỗi lần gọi đệ quy = 1 frame trên call stack
  
  if (left > right) return -1;
  
  int mid = (left + right) ~/ 2;
  
  if (arr[mid] == target) return mid;
  else if (arr[mid] < target) 
    return binarySearchRecursive(arr, target, mid + 1, right);
  else 
    return binarySearchRecursive(arr, target, left, mid - 1);
}

Swift


func binarySearchRecursive(_ arr: [Int], _ target: Int, _ left: Int, _ right: Int) -> Int {
    // Mỗi lần gọi đệ quy = 1 frame trên call stack
    
    if left > right { return -1 }
    
    let mid = (left + right) / 2
    
    if arr[mid] == target { return mid }
    else if arr[mid] < target {
        return binarySearchRecursive(arr, target, mid + 1, right)
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1)
    }
}

Java


int binarySearchRecursive(int[] arr, int target, int left, int right) {
    // Mỗi lần gọi đệ quy = 1 frame trên call stack
    
    if (left > right) return -1;
    
    int mid = (left + right) / 2;
    
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearchRecursive(arr, target, mid + 1, right);
    else
        return binarySearchRecursive(arr, target, left, mid - 1);
}

Phân tích Call Stack:

Lần gọi	Kích thước vùng tìm	Stack frames
1	n	1
2	n/2	2
3	n/4	3
k	n/2^(k-1)	k

Dừng khi: n/2^(k-1) = 1 → k = log₂n

Space: O(log n) cho call stack

💡

Đệ quy luôn tốn thêm bộ nhớ cho call stack! Binary Search iterative chỉ cần O(1) space.

Ví dụ 5: O(n) Space - Đệ quy tuyến tính

Bài toán

Tính giai thừa bằng đệ quy.

Python


def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
# factorial(5)
# Call stack:
#   factorial(5) đang chờ
#   factorial(4) đang chờ
#   factorial(3) đang chờ
#   factorial(2) đang chờ
#   factorial(1) = 1 ← trả về

Kotlin


fun factorial(n: Int): Long {
    if (n <= 1) return 1
    return n * factorial(n - 1)
}
 
// Call stack: n frames

Dart


int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
 
// Call stack: n frames

Swift


func factorial(_ n: Int) -> Int {
    if n <= 1 { return 1 }
    return n * factorial(n - 1)
}
 
// Call stack: n frames

Java


long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
 
// Call stack: n frames

Phân tích Call Stack:

factorial(n) gọi factorial(n-1)
factorial(n-1) gọi factorial(n-2)
…
factorial(1) trả về

Số frames tối đa: n frames → O(n) space

So sánh với Iterative

Python


def factorial_iterative(n):
    result = 1          # 1 biến
    for i in range(2, n + 1):
        result *= i
    return result
# Space: O(1) - chỉ cần 2 biến

Kotlin


fun factorialIterative(n: Int): Long {
    var result = 1L
    for (i in 2..n) {
        result *= i
    }
    return result
}
// Space: O(1)

Dart


int factorialIterative(int n) {
  int result = 1;
  for (int i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
// Space: O(1)

Swift


func factorialIterative(_ n: Int) -> Int {
    var result = 1
    for i in 2...n {
        result *= i
    }
    return result
}
// Space: O(1)

Java


long factorialIterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
// Space: O(1)

Ví dụ 6: O(n²) Space - Ma trận 2D

Bài toán

Tạo bảng nhân n×n.

Python


def multiplication_table(n):
    # Tạo ma trận n x n
    table = []
    
    for i in range(1, n + 1):
        row = []                  # n rows
        for j in range(1, n + 1):
            row.append(i * j)     # n columns mỗi row
        table.append(row)
    
    return table
# Tổng: n × n = n² phần tử → O(n²) space

Kotlin


fun multiplicationTable(n: Int): List<List<Int>> {
    return (1..n).map { i ->
        (1..n).map { j -> i * j }
    }
}
// Tổng: n × n = n² phần tử → O(n²) space

Dart


List<List<int>> multiplicationTable(int n) {
  return List.generate(n, (i) => 
    List.generate(n, (j) => (i + 1) * (j + 1))
  );
}
// Tổng: n × n = n² phần tử → O(n²) space

Swift


func multiplicationTable(_ n: Int) -> [[Int]] {
    return (1...n).map { i in
        (1...n).map { j in i * j }
    }
}
// Tổng: n × n = n² phần tử → O(n²) space

Java


int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}
// Tổng: n × n = n² phần tử → O(n²) space

Phân tích:

Ma trận có n rows
Mỗi row có n columns
Tổng: n × n = n² phần tử

Space: O(n²)

Bảng tóm tắt

Ví dụ	Auxiliary Space	Lý do
Reverse in-place	O(1)	Chỉ dùng vài biến
Reverse copy	O(n)	Tạo mảng mới n phần tử
Two Sum (brute)	O(1)	Không có cấu trúc phụ
Two Sum (hash)	O(n)	Set chứa n phần tử
Binary Search (recursive)	O(log n)	Call stack log n levels
Factorial (recursive)	O(n)	Call stack n levels
Factorial (iterative)	O(1)	Chỉ biến đếm
Ma trận n×n	O(n²)	n² phần tử

Tips phân tích Space Complexity

📌

Checklist phân tích Space:

Biến đơn (int, float, bool): O(1)
Mảng/List kích thước n: O(n)
Ma trận n×n: O(n²)
Hash Table/Set với n keys: O(n)
Đệ quy: Đếm max call stack depth

Tiếp theo: Mảng (Array)