Giới thiệu

Chào mừng bạn đến với bài viết về độ phức tạp thời gian Big O! Trong bài viết này, chúng ta sẽ tìm hiểu về các lớp Big O phổ biến thông qua các ví dụ cụ thể bằng ngôn ngữ lập trình Go. Việc hiểu rõ về Big O là rất quan trọng trong lập trình, giúp bạn tối ưu hóa mã nguồn và cải thiện hiệu suất ứng dụng.

Mục lục

• O(n) - Thời gian tuyến tính
• O(log n) - Thời gian logarithmic
• O(n log n) - Thời gian điển hình của các thuật toán sắp xếp hiệu quả
• O(n²) - Thời gian bình phương
• O(2ⁿ) - Thời gian mũ
• O(n!) - Thời gian giai thừa
• O(1) - Thời gian hằng số
• Các quy tắc và lưu ý cho người mới bắt đầu

O(n) - Thời gian tuyến tính

Ví dụ: Tìm kiếm tuyến tính (linear search) trong mảng.

// Tìm kiếm tuyến tính: O(n)
func linearSearch(nums []int, target int) int {
    for i := 0; i < len(nums); i++ { // thực hiện tối đa n lần
        if nums[i] == target { // so sánh thời gian hằng số mỗi lần lặp
            return i
        }
    }
    return -1
}

Giải thích từng bước

• n là kích thước của đầu vào, tức là độ dài của nums.
• Trong trường hợp xấu nhất (khi không tìm thấy hoặc tìm thấy ở phần tử cuối), vòng lặp for sẽ thực hiện n lần.
• Mỗi lần lặp (trong vòng lặp) thực hiện công việc O(1) (so sánh và có thể gán).
• Độ phức tạp lớn là O(1 * n) = O(n).

O(log n) - Thời gian logarithmic

Ví dụ: Tìm kiếm nhị phân (binary search) trong một mảng đã sắp xếp.

// Tìm kiếm nhị phân: O(log n)
func binarySearch(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2 // cắt khoảng tìm kiếm còn một nửa
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

Giải thích từng bước

• Mỗi lần lặp, khoảng tìm kiếm sẽ được giảm một nửa.
• Sau k lần lặp, kích thước khoảng còn lại khoảng n / 2^k.
• Nó dừng lại khi n / 2^k ≤ 1 → 2^k ≥ n → k ≥ log₂(n).
• Số lần lặp ~ ⌈log₂ n⌉ → O(log n).
• Lưu ý: cơ sở của logarithm không quan trọng trong Big-O (log₂, log₁₀, ln đều là Θ(log n)).

O(n log n) - Thời gian điển hình của các thuật toán sắp xếp hiệu quả

Ví dụ: Thuật toán sắp xếp hợp nhất (merge sort).

// Sắp xếp hợp nhất: O(n log n)
func mergeSort(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    mid := len(a) / 2
    left := mergeSort(a[:mid])
    right := mergeSort(a[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    res := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            res = append(res, left[i])
            i++
        } else {
            res = append(res, right[j])
            j++
        }
    }
    // thêm phần còn lại
    res = append(res, left[i:]...)
    res = append(res, right[j:]...)
    return res
}

Giải thích từng bước

• Công thức hồi quy: T(n) = 2·T(n/2) + O(n) (vì chúng ta sắp xếp hai nửa rồi hợp nhất trong O(n)).
• Sử dụng Định lý Master hoặc tính toán chi phí theo từng cấp:
  • Cấp 0 (gốc): chi phí O(n) để hợp nhất tại cấp đó,
  • Cấp 1: hai lần hợp nhất kích thước n/2 → tổng O(n),
  • Cấp 2: bốn lần hợp nhất kích thước n/4 → tổng O(n),
  • ... có khoảng log₂(n) cấp.
• Tổng ≈ n * (log₂(n) + 1) → O(n log n).

O(n²) - Thời gian bình phương

Ví dụ: In ra mọi cặp (nested loops).

// In ra mọi cặp: O(n²)
func printPairs(nums []int) {
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            // công việc thời gian hằng số bên trong
            _ = nums[i] + nums[j]  // giả sử chúng ta thực hiện công việc O(1)
        }
    }
}

Giải thích từng bước

• Vòng lặp ngoài chạy n lần.
• Đối với mỗi lần lặp bên ngoài, vòng lặp bên trong chạy n lần.
• Tổng số lần lặp = n * n = n².
• Bỏ qua các hằng số và các thuật ngữ bậc thấp → O(n²).

O(2ⁿ) - Thời gian mũ (base 2)

Ví dụ: Tạo tất cả các tập hợp con (power set).

// Tạo tất cả các tập hợp con: O(2^n)
func subsets(nums []int) [][]int {
    res := [][]int{}
    var helper func(int, []int)
    helper = func(i int, cur []int) {
        if i == len(nums) {
            tmp := append([]int(nil), cur...)
            res = append(res, tmp)
            return
        }
        // loại trừ phần tử hiện tại
        helper(i+1, cur)
        // bao gồm phần tử hiện tại
        helper(i+1, append(cur, nums[i]))
    }
    helper(0, []int{})
    return res
}

Giải thích từng bước

• Tại mỗi chỉ số i, bạn phân nhánh thành hai cuộc gọi (bao gồm / loại trừ).
• Độ sâu của cây = n, hệ số phân nhánh = 2 → số lá = 2ⁿ.
• Bạn thực hiện ít nhất một công việc hằng số cho mỗi lá (cộng thêm chi phí để xây dựng mỗi tập hợp con).
• Tổng công việc ≈ c · 2ⁿ → O(2ⁿ).

O(n!) - Thời gian giai thừa

Ví dụ: Tạo tất cả các hoán vị của n phần tử khác nhau.

// Tạo tất cả các hoán vị: O(n!)
func permutations(nums []int) [][]int {
    a := make([]int, len(nums))
    copy(a, nums)
    res := [][]int{}
    var helper func(int)
    helper = func(k int) {
        if k == len(a)-1 {
            tmp := append([]int(nil), a...)
            res = append(res, tmp)
            return
        }
        for i := k; i < len(a); i++ {
            a[k], a[i] = a[i], a[k] // hoán đổi
            helper(k + 1)
            a[k], a[i] = a[i], a[k] // hoán đổi lại
        }
    }
    helper(0)
    return res
}

Giải thích từng bước

• Số lượng hoán vị của n phần tử khác nhau là n! = n × (n−1) × (n−2) × ... × 1.
• Đệ quy sản xuất tất cả n! hoán vị.

O(1) - Thời gian hằng số

Ví dụ: Lấy phần tử đầu tiên của một mảng.

// O(1) - truy cập phần tử đầu tiên
func getFirst(nums []int) int {
    if len(nums) == 0 {
        return -1
    }
    return nums[0] // thực hiện một phép toán duy nhất
}

Giải thích từng bước

1. Giả sử n = len(nums).
2. Hàm thực hiện:

• Một kiểm tra: len(nums) == 0 → O(1)
• Một truy cập chỉ số: nums[0] → O(1)
• Một trả về → O(1)

Tổng số phép toán = 3 (hoặc một hằng số nhỏ c). Không phụ thuộc vào n.
Vì vậy, thời gian thực thi = O(1) — nó giữ nguyên ngay cả khi nums có 1 phần tử hoặc 1 triệu phần tử.

Lưu ý quan trọng

Các thuật toán thời gian hằng số thực hiện một số bước cố định bất kể kích thước đầu vào.

Các quy tắc và lưu ý cho người mới bắt đầu

• Bỏ qua các hằng số: c·n → O(n). 5n² → O(n²).
• Bỏ qua các thuật ngữ bậc thấp: (n² + n)/2 → O(n²).
• Cơ sở logarithm không quan trọng: log₂ n, log₁₀ n, ln n đều là Θ(log n).
• Quy tắc nhân: vòng lặp lồng nhau (n × n) → O(n²).
• Quy tắc cộng: nếu bạn thực hiện O(n) sau đó O(n²), tổng là O(n + n²) → O(n²) (giữ lại thuật ngữ thống trị).
• Đệ quy chia và chinh phục thường cho O(n log n) hoặc O(log n) tùy thuộc vào việc phân tách và hợp nhất (sử dụng Định lý Master hoặc tính chi phí theo từng cấp).
• Kích thước đầu ra cũng quan trọng: việc tạo ra tất cả các tổ hợp/tập hợp/hoán vị có nghĩa là thời gian thực thi tăng ít nhất nhanh như số lượng đầu ra (2ⁿ, n!, ...).

Kết luận

Hi vọng qua bài viết này, bạn đã có cái nhìn tổng quan về độ phức tạp thời gian Big O và cách tính toán nó trong các thuật toán lập trình. Việc nắm vững các khái niệm này sẽ giúp bạn cải thiện kỹ năng lập trình và tối ưu hóa mã nguồn hiệu quả hơn. Nếu bạn có bất kỳ câu hỏi nào, đừng ngần ngại để lại câu hỏi ở phần bình luận bên dưới nhé!