Độ phức tạp thuật toán (Big O Notation)

Big O là gì?

Big O Notation là cách đo lường hiệu suất của thuật toán dựa trên:

Thời gian (Time Complexity): Thuật toán chạy nhanh hay chậm?
Không gian (Space Complexity): Thuật toán dùng bao nhiêu bộ nhớ?

💡

Big O mô tả trường hợp xấu nhất (worst case) và cho biết thuật toán sẽ “scale” như thế nào khi dữ liệu tăng lên.

Các độ phức tạp phổ biến

Big O	Tên gọi	Ví dụ
O(1)	Constant	Truy cập phần tử mảng
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Duyệt mảng
O(n log n)	Linearithmic	Merge Sort, Quick Sort
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Fibonacci đệ quy
O(n!)	Factorial	Permutations

O(1) - Constant Time

Thời gian thực thi không đổi dù dữ liệu lớn đến đâu.

Python


def get_first(arr):
    return arr[0]  # O(1)
 
def add_numbers(a, b):
    return a + b  # O(1)
 
# Hash table lookup
my_dict = {"name": "John", "age": 30}
print(my_dict["name"])  # O(1)

Kotlin


fun getFirst(arr: List<Int>): Int = arr[0]  // O(1)
 
fun addNumbers(a: Int, b: Int): Int = a + b  // O(1)
 
// Hash table lookup
val myMap = mapOf("name" to "John", "age" to 30)
println(myMap["name"])  // O(1)

Dart


int getFirst(List<int> arr) => arr[0];  // O(1)
 
int addNumbers(int a, int b) => a + b;  // O(1)
 
// Hash table lookup
var myMap = {"name": "John", "age": 30};
print(myMap["name"]);  // O(1)

Swift


func getFirst(_ arr: [Int]) -> Int { arr[0] }  // O(1)
 
func addNumbers(_ a: Int, _ b: Int) -> Int { a + b }  // O(1)
 
// Hash table lookup
let myDict = ["name": "John", "age": "30"]
print(myDict["name"]!)  // O(1)

Java


int getFirst(int[] arr) { return arr[0]; }  // O(1)
 
int addNumbers(int a, int b) { return a + b; }  // O(1)
 
// Hash table lookup
Map<String, Object> myMap = new HashMap<>();
myMap.put("name", "John");
System.out.println(myMap.get("name"));  // O(1)

O(log n) - Logarithmic Time

Mỗi bước chia đôi dữ liệu cần xử lý.

Python


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Kotlin


fun binarySearch(arr: List<Int>, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    
    while (left <= right) {
        val mid = (left + right) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

Dart


int binarySearch(List<int> arr, int target) {
  int left = 0, right = arr.length - 1;
  
  while (left <= right) {
    int mid = (left + right) ~/ 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Swift


func binarySearch(_ arr: [Int], _ target: Int) -> Int {
    var left = 0, right = arr.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        if arr[mid] == target { return mid }
        else if arr[mid] < target { left = mid + 1 }
        else { right = mid - 1 }
    }
    return -1
}

Java


int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

O(n) - Linear Time

Thời gian tăng tỷ lệ thuận với kích thước dữ liệu.

Python


def find_max(arr):
    max_val = arr[0]
    for num in arr:  # Duyệt n phần tử
        if num > max_val:
            max_val = num
    return max_val

Kotlin


fun findMax(arr: List<Int>): Int {
    var maxVal = arr[0]
    for (num in arr) {  // Duyệt n phần tử
        if (num > maxVal) maxVal = num
    }
    return maxVal
}

Dart


int findMax(List<int> arr) {
  int maxVal = arr[0];
  for (int num in arr) {  // Duyệt n phần tử
    if (num > maxVal) maxVal = num;
  }
  return maxVal;
}

Swift


func findMax(_ arr: [Int]) -> Int {
    var maxVal = arr[0]
    for num in arr {  // Duyệt n phần tử
        if num > maxVal { maxVal = num }
    }
    return maxVal
}

Java


int findMax(int[] arr) {
    int maxVal = arr[0];
    for (int num : arr) {  // Duyệt n phần tử
        if (num > maxVal) maxVal = num;
    }
    return maxVal;
}

O(n²) - Quadratic Time

Thường do nested loops - vòng lặp lồng nhau.

Python


def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # O(n)
        for j in range(n - 1):   # O(n)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
# Tổng: O(n × n) = O(n²)

Kotlin


fun bubbleSort(arr: MutableList<Int>): List<Int> {
    val n = arr.size
    for (i in 0 until n) {           // O(n)
        for (j in 0 until n - 1) {   // O(n)
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

Dart


List<int> bubbleSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n; i++) {           // O(n)
    for (int j = 0; j < n - 1; j++) {     // O(n)
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

Swift


func bubbleSort(_ arr: inout [Int]) {
    let n = arr.count
    for _ in 0..<n {                    // O(n)
        for j in 0..<(n - 1) {          // O(n)
            if arr[j] > arr[j + 1] {
                arr.swapAt(j, j + 1)
            }
        }
    }
}

Java


void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {           // O(n)
        for (int j = 0; j < n - 1; j++) {   // O(n)
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

⚠️

O(n²) trở lên thường không chấp nhận được với dữ liệu lớn. Hãy tìm cách tối ưu!

Space Complexity

Bộ nhớ sử dụng theo kích thước input.

Python


# O(1) Space - In-place
def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
 
# O(n) Space - Tạo mảng mới
def reverse_copy(arr):
    return arr[::-1]  # Tạo bản sao mới

Kotlin


// O(1) Space - In-place
fun reverseInplace(arr: MutableList<Int>) {
    var left = 0
    var right = arr.size - 1
    while (left < right) {
        val temp = arr[left]
        arr[left] = arr[right]
        arr[right] = temp
        left++; right--
    }
}
 
// O(n) Space - Tạo list mới
fun reverseCopy(arr: List<Int>) = arr.reversed()

Dart


// O(1) Space - In-place
void reverseInplace(List<int> arr) {
  int left = 0, right = arr.length - 1;
  while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++; right--;
  }
}
 
// O(n) Space - Tạo list mới
List<int> reverseCopy(List<int> arr) => arr.reversed.toList();

Swift


// O(1) Space - In-place
func reverseInplace(_ arr: inout [Int]) {
    var left = 0, right = arr.count - 1
    while left < right {
        arr.swapAt(left, right)
        left += 1; right -= 1
    }
}
 
// O(n) Space - Tạo array mới
func reverseCopy(_ arr: [Int]) -> [Int] { arr.reversed() }

Java


// O(1) Space - In-place
void reverseInplace(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++; right--;
    }
}
 
// O(n) Space - Tạo array mới  
int[] reverseCopy(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        result[i] = arr[arr.length - 1 - i];
    }
    return result;
}

Quy tắc tính Big O

1. Bỏ qua hằng số (Drop Constants)

Khi phân tích Big O, ta bỏ qua các hằng số nhân vì chúng không ảnh hưởng đến tốc độ tăng của thuật toán.

Giải thích: O(2n), O(3n), O(100n) đều tăng tuyến tính theo n, nên đều quy về O(n).

Python


def example(arr):
    # Duyệt mảng 1 lần: n phép
    for x in arr:
        print(x)
    
    # Duyệt mảng lần 2: n phép
    for x in arr:
        print(x * 2)
 
# Tổng: 2n phép → O(2n) → O(n)

Kotlin


fun example(arr: List<Int>) {
    // Duyệt mảng 1 lần: n phép
    for (x in arr) println(x)
    
    // Duyệt mảng lần 2: n phép
    for (x in arr) println(x * 2)
}
// Tổng: 2n phép → O(2n) → O(n)

Dart


void example(List<int> arr) {
  // Duyệt mảng 1 lần: n phép
  for (var x in arr) print(x);
  
  // Duyệt mảng lần 2: n phép
  for (var x in arr) print(x * 2);
}
// Tổng: 2n phép → O(2n) → O(n)

Swift


func example(_ arr: [Int]) {
    // Duyệt mảng 1 lần: n phép
    for x in arr { print(x) }
    
    // Duyệt mảng lần 2: n phép
    for x in arr { print(x * 2) }
}
// Tổng: 2n phép → O(2n) → O(n)

Java


void example(int[] arr) {
    // Duyệt mảng 1 lần: n phép
    for (int x : arr) System.out.println(x);
    
    // Duyệt mảng lần 2: n phép
    for (int x : arr) System.out.println(x * 2);
}
// Tổng: 2n phép → O(2n) → O(n)

2. Giữ lại số hạng lớn nhất (Drop Non-Dominant Terms)

Khi có nhiều số hạng, chỉ giữ lại số hạng tăng nhanh nhất vì nó sẽ “thống trị” khi n lớn.

Giải thích: Với n = 1000: n² = 1,000,000 nhưng n chỉ = 1000. Số hạng n “không đáng kể” so với n².

Biểu thức	Đơn giản
O(n² + n)	O(n²)
O(n³ + n² + n)	O(n³)
O(n + log n)	O(n)
O(2ⁿ + n²)	O(2ⁿ)

Python


def example(arr):
    n = len(arr)
    
    # Phần 1: O(n²)
    for i in range(n):
        for j in range(n):
            print(i, j)
    
    # Phần 2: O(n)
    for i in range(n):
        print(i)
 
# Tổng: O(n² + n) → O(n²)

Kotlin


fun example(arr: List<Int>) {
    val n = arr.size
    
    // Phần 1: O(n²)
    for (i in 0 until n)
        for (j in 0 until n)
            println("$i $j")
    
    // Phần 2: O(n)
    for (i in 0 until n) println(i)
}
// Tổng: O(n² + n) → O(n²)

Dart


void example(List<int> arr) {
  int n = arr.length;
  
  // Phần 1: O(n²)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      print("$i $j");
  
  // Phần 2: O(n)
  for (int i = 0; i < n; i++) print(i);
}
// Tổng: O(n² + n) → O(n²)

Swift


func example(_ arr: [Int]) {
    let n = arr.count
    
    // Phần 1: O(n²)
    for i in 0..<n {
        for j in 0..<n { print("\(i) \(j)") }
    }
    
    // Phần 2: O(n)
    for i in 0..<n { print(i) }
}
// Tổng: O(n² + n) → O(n²)

Java


void example(int[] arr) {
    int n = arr.length;
    
    // Phần 1: O(n²)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            System.out.println(i + " " + j);
    
    // Phần 2: O(n)
    for (int i = 0; i < n; i++) System.out.println(i);
}
// Tổng: O(n² + n) → O(n²)

3. Các phép toán liên tiếp = Cộng (Add for Sequential)

Khi có nhiều đoạn code chạy tuần tự (không lồng nhau), ta cộng độ phức tạp.

Giải thích: Nếu duyệt mảng A kích thước a, rồi duyệt mảng B kích thước b → O(a + b).

Python


def process_two_arrays(arr1, arr2):
    # Duyệt arr1: O(a) với a = len(arr1)
    for x in arr1:
        print(x)
    
    # Duyệt arr2: O(b) với b = len(arr2)
    for y in arr2:
        print(y)
 
# Tổng: O(a) + O(b) = O(a + b)
# LƯU Ý: Không phải O(n) vì 2 mảng có kích thước khác nhau!

Kotlin


fun processTwoArrays(arr1: List<Int>, arr2: List<Int>) {
    // Duyệt arr1: O(a)
    for (x in arr1) println(x)
    
    // Duyệt arr2: O(b)
    for (y in arr2) println(y)
}
// Tổng: O(a + b)

Dart


void processTwoArrays(List<int> arr1, List<int> arr2) {
  // Duyệt arr1: O(a)
  for (var x in arr1) print(x);
  
  // Duyệt arr2: O(b)
  for (var y in arr2) print(y);
}
// Tổng: O(a + b)

Swift


func processTwoArrays(_ arr1: [Int], _ arr2: [Int]) {
    // Duyệt arr1: O(a)
    for x in arr1 { print(x) }
    
    // Duyệt arr2: O(b)
    for y in arr2 { print(y) }
}
// Tổng: O(a + b)

Java


void processTwoArrays(int[] arr1, int[] arr2) {
    // Duyệt arr1: O(a)
    for (int x : arr1) System.out.println(x);
    
    // Duyệt arr2: O(b)
    for (int y : arr2) System.out.println(y);
}
// Tổng: O(a + b)

4. Vòng lặp lồng nhau = Nhân (Multiply for Nested)

Khi có vòng lặp lồng bên trong vòng lặp khác, ta nhân độ phức tạp.

Giải thích: Vòng ngoài chạy a lần, mỗi lần vòng trong chạy b lần → Tổng: a × b lần.

Python


def nested_loops(arr1, arr2):
    # Với mỗi phần tử của arr1 (a lần)
    for x in arr1:
        # Duyệt toàn bộ arr2 (b lần)
        for y in arr2:
            print(x, y)
 
# Tổng: O(a × b)
# Nếu a = b = n thì O(n²)

Kotlin


fun nestedLoops(arr1: List<Int>, arr2: List<Int>) {
    // Với mỗi phần tử của arr1 (a lần)
    for (x in arr1) {
        // Duyệt toàn bộ arr2 (b lần)
        for (y in arr2) {
            println("$x $y")
        }
    }
}
// Tổng: O(a × b)

Dart


void nestedLoops(List<int> arr1, List<int> arr2) {
  // Với mỗi phần tử của arr1 (a lần)
  for (var x in arr1) {
    // Duyệt toàn bộ arr2 (b lần)
    for (var y in arr2) {
      print("$x $y");
    }
  }
}
// Tổng: O(a × b)

Swift


func nestedLoops(_ arr1: [Int], _ arr2: [Int]) {
    // Với mỗi phần tử của arr1 (a lần)
    for x in arr1 {
        // Duyệt toàn bộ arr2 (b lần)
        for y in arr2 {
            print("\(x) \(y)")
        }
    }
}
// Tổng: O(a × b)

Java


void nestedLoops(int[] arr1, int[] arr2) {
    // Với mỗi phần tử của arr1 (a lần)
    for (int x : arr1) {
        // Duyệt toàn bộ arr2 (b lần)
        for (int y : arr2) {
            System.out.println(x + " " + y);
        }
    }
}
// Tổng: O(a × b)

⚠️

Phân biệt O(a + b) và O(a × b):

Tuần tự (sequential): for A rồi for B → O(a + b)
Lồng nhau (nested): for A { for B } → O(a × b)

Tóm tắt

Cần nhớ
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Nested loops → O(n²)
Chia đôi mỗi bước → O(log n)
Tối ưu từ O(n²) → O(n) thường dùng Hash Table

Tiếp theo: Mảng (Array)