Độ Phức Tạp Thuật Toán — Big O, Omega, Theta & Amortized

Năm 2012, một hệ thống xếp hàng thương mại điện tử xử lý 500 đơn/giây bằng thuật toán đối soát $O(N^2)$ hoạt động hoàn hảo — cho đến ngày flash sale khi đơn hàng vọt lên 50.000/giây. Thời gian xử lý nhảy từ 250ms sang hơn 40 phút cho một batch. Hệ thống sập, mất doanh thu, mất niềm tin khách hàng. Nguyên nhân gốc rễ không phải server yếu — mà là kỹ sư không hiểu rằng khi $N$ tăng 100 lần, thuật toán $O(N^2)$ chậm đi 10.000 lần.

Phân tích độ phức tạp không phải kiến thức hàn lâm để qua vòng phỏng vấn. Nó là công cụ dự báo giúp bạn phân biệt giữa code "chạy được trên laptop" và code "sống được trên production". Kỹ sư giỏi không đoán — họ tính. Họ nhìn vào vòng lặp lồng nhau và thấy ngay mối nguy khi dữ liệu scale lên. Họ chọn cấu trúc dữ liệu dựa trên ràng buộc thời gian thực, không phải dựa trên thói quen.

Bài viết này trang bị cho bạn toàn bộ khung tư duy: từ ký hiệu tiệm cận (Big O, Ω, Θ) đến amortized analysis, từ bảng tra thực tế đến kỹ thuật suy luận complexity bằng tay — cùng những sai lầm mà ngay cả kỹ sư nhiều năm kinh nghiệm vẫn mắc phải.

Bức tranh tư duy

Hãy hình dung bạn đang vận hành một quán phở ở Sài Gòn.

$O(1)$ — Khách gọi "phở tái", bạn múc ngay từ nồi sẵn. Dù 1 hay 1.000 khách, mỗi tô vẫn mất đúng 10 giây.

$O(N)$ — Khách yêu cầu kiểm tra xem có ai tên Minh trong hàng chờ không. Bạn phải đi hỏi từng người, tệ nhất là hỏi hết cả hàng.

$O(N^2)$ — Chủ quán muốn so sánh từng cặp khách xem ai quen ai. 10 khách thì 45 cặp, nhưng 1.000 khách thì gần nửa triệu cặp — quán đóng cửa trước khi kiểm xong.

$O(\log N)$ — Danh sách khách VIP đã xếp theo alphabet. Tìm tên "Nguyễn Văn A" bằng cách mở giữa danh sách, rồi lấy nửa phù hợp — mỗi lần loại bỏ một nửa. 1 triệu tên chỉ cần ~20 lần tra.

$O(2^N)$ — Thực đơn có N món, quán muốn liệt kê mọi combo có thể. 20 món = hơn 1 triệu combo. 30 món = hơn 1 tỷ. Quán phá sản vì in menu.

Tốc độ tăng trưởng khi N tăng:
──────────────────────────────────────────────
N       │ O(1) │ O(logN) │ O(N)  │ O(NlogN)  │ O(N²)       │ O(2^N)
────────┼──────┼─────────┼───────┼───────────┼─────────────┼──────────────
10      │ 1    │ 3       │ 10    │ 33        │ 100         │ 1.024
100     │ 1    │ 7       │ 100   │ 664       │ 10.000      │ 1,27 × 10³⁰
10.000  │ 1    │ 13      │ 10K   │ 132K      │ 100.000.000 │ ∞
1M      │ 1    │ 20      │ 1M    │ 20M       │ 10¹²        │ ∞
──────────────────────────────────────────────
Giả sử 1 phép toán = 1 nanosecond (10⁻⁹s):
• O(N²) với N=1M → 10¹² ns ≈ 16,7 phút
• O(NlogN) với N=1M → 20M ns ≈ 0,02 giây

Thông điệp cốt lõi: sự khác biệt giữa các lớp complexity không phải "hơi nhanh hơn" — mà là chạy được versus không chạy được.

Cốt lõi kỹ thuật

Ký hiệu tiệm cận — Bộ ba O, Ω, Θ

Ba ký hiệu này mô tả hành vi của hàm khi đầu vào tiến tới vô cùng. Chúng không đo thời gian chạy cụ thể — chúng mô tả tốc độ tăng trưởng.

Ký hiệu	Ý nghĩa	Diễn giải thực tế
$O(f(N))$	Cận trên (upper bound)	"Tệ nhất thì tăng nhanh bằng $f(N)$"
$\mathrm{\Omega }(f(N))$	Cận dưới (lower bound)	"Ít nhất cũng phải mất $f(N)$"
$\mathrm{\Theta }(f(N))$	Cận chặt (tight bound)	"Tăng trưởng đúng theo $f(N)$"

Định nghĩa hình thức: $f(N)=O(g(N))$ nếu tồn tại hằng số $c>0$ và $N_0$ sao cho với mọi $N\ge N_0$: $f(N)\le c\cdot g(N)$.

Trong thực hành kỹ thuật, hầu hết mọi người dùng Big O theo nghĩa "tight bound" — khi nói thuật toán là $O(N\log N)$ thường ngụ ý nó cũng là $\mathrm{\Theta }(N\log N)$. Tuy nhiên, phân biệt chính xác giữa worst-case ($O$), best-case ($\mathrm{\Omega }$), và average-case là kỹ năng thiết yếu khi đánh giá thuật toán cho production.

Phân loại đầy đủ các lớp complexity

Lớp	Tên	Ví dụ thuật toán	Khả thi với N?
$O(1)$	Hằng số	Hash table lookup, stack push/pop	N bất kỳ
$O(\log N)$	Logarit	Binary search, cây AVL/Red-Black	N bất kỳ
$O(\sqrt{N})$	Căn bậc hai	Trial division, Mo's algorithm	$N\le {10}^{16}$
$O(N)$	Tuyến tính	Linear scan, counting sort	$N\le {10}^8$
$O(N\log N)$	Tuyến tính-logarit	Merge sort, FFT	$N\le {10}^7$
$O(N^2)$	Bình phương	Insertion sort, so sánh mọi cặp	$N\le {10}^4$
$O(N^3)$	Lập phương	Floyd-Warshall, nhân ma trận naive	$N\le 500$
$O(2^N)$	Hàm mũ	Subset enumeration, brute-force TSP	$N\le 20-25$
$O(N!)$	Giai thừa	Liệt kê hoán vị	$N\le 10-12$

Cột "Khả thi với N" giả định giới hạn thời gian 1-2 giây trên máy hiện đại (~${10}^8$ phép toán/giây cho các phép toán đơn giản). Đây là kim chỉ nam cực kỳ hữu ích khi đọc đề bài competitive programming hoặc ước lượng cho production.

Time Complexity vs Space Complexity

Mỗi thuật toán tiêu tốn hai loại tài nguyên: thời gian (CPU cycles) và không gian (bộ nhớ). Phân tích complexity áp dụng cho cả hai.

Thuật toán	Time	Space	Ghi chú
Merge Sort	$O(N\log N)$	$O(N)$	Cần mảng phụ
Quick Sort (in-place)	$O(N\log N)$ avg	$O(\log N)$	Stack đệ quy
Heap Sort	$O(N\log N)$	$O(1)$	In-place
Hash Table lookup	$O(1)$ avg	$O(N)$	Đánh đổi bộ nhớ lấy tốc độ
DFS trên đồ thị	$O(V+E)$	$O(V)$	Stack/recursion depth

Quy tắc đánh đổi kinh điển: Time-Space Tradeoff. Bạn thường có thể tăng tốc thuật toán bằng cách dùng thêm bộ nhớ (memoization, caching, bảng tra cứu) hoặc tiết kiệm bộ nhớ bằng cách chấp nhận tính toán lại (streaming, on-the-fly computation).

Amortized Analysis — Khi worst-case nói dối

Một số cấu trúc dữ liệu có thao tác thỉnh thoảng chậm nhưng trung bình rất nhanh. Amortized analysis đo chi phí trung bình trên một chuỗi $N$ thao tác, thay vì nhìn vào từng thao tác riêng lẻ.

Ví dụ kinh điển: dynamic array (C++ vector, Java ArrayList, Python list). Khi push phần tử:

• Hầu hết lần push: $O(1)$ — ghi vào ô trống có sẵn.
• Khi hết chỗ: phải cấp phát mảng gấp đôi, copy toàn bộ → $O(N)$.
• Nhưng vì mỗi lần resize gấp đôi, cần $N$ lần push nữa mới phải resize tiếp.
• Amortized cost: $O(1)$ per push.

C++ — Minh họa amortized

#include <iostream>
#include <chrono>
#include <vector>

// Minh họa: push N phần tử vào vector
// Tổng chi phí resize là O(N), chia đều cho N lần push → O(1) amortized
void demonstrateAmortized(int n) {
    std::vector<int> v;
    int resizeCount = 0;
    size_t prevCapacity = v.capacity();

    for (int i = 0; i < n; ++i) {
        v.push_back(i);
        if (v.capacity() != prevCapacity) {
            ++resizeCount;
            prevCapacity = v.capacity();
        }
    }
    // N = 1.000.000 → resizeCount ≈ 20 (log2(N))
    std::cout << "N=" << n << ", resizes=" << resizeCount
              << ", final capacity=" << v.capacity() << "\n";
}

int main() {
    demonstrateAmortized(1'000'000);
    return 0;
}

Python — Minh họa amortized

import sys

def demonstrate_amortized(n: int) -> None:
    """Push N phần tử vào list, đếm số lần thay đổi kích thước internal."""
    items: list[int] = []
    resize_count = 0
    prev_size = sys.getsizeof(items)

    for i in range(n):
        items.append(i)
        current_size = sys.getsizeof(items)
        if current_size != prev_size:
            resize_count += 1
            prev_size = current_size

    print(f"N={n}, resizes={resize_count}, final len={len(items)}")

# N = 1_000_000 → resize_count nhỏ hơn nhiều so với N
demonstrate_amortized(1_000_000)

Java — Minh họa amortized

import java.util.ArrayList;

public class AmortizedDemo {
    public static void main(String[] args) {
        int n = 1_000_000;
        ArrayList<Integer> list = new ArrayList<>();

        // ArrayList mặc định capacity = 10, grow factor = 1.5x
        // Amortized O(1) per add — tuy worst-case single add là O(N)
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        long elapsed = System.nanoTime() - start;

        System.out.printf("N=%d, time=%.2fms, avg=%.0fns/op%n",
            n, elapsed / 1e6, (double) elapsed / n);
    }
}

Go — Minh họa amortized

package main

import "fmt"

func demonstrateAmortized(n int) {
	s := make([]int, 0)
	resizeCount := 0
	prevCap := cap(s)

	for i := 0; i < n; i++ {
		s = append(s, i)
		if cap(s) != prevCap {
			resizeCount++
			prevCap = cap(s)
		}
	}
	// Go slice grow factor ≈ 2x (nhỏ) hoặc 1.25x (lớn)
	fmt.Printf("N=%d, resizes=%d, final cap=%d\n", n, resizeCount, cap(s))
}

func main() {
	demonstrateAmortized(1_000_000)
}

Ba phương pháp amortized analysis phổ biến:

Phương pháp	Ý tưởng	Khi nào dùng
Aggregate	Tổng chi phí N thao tác chia N	Đơn giản, dễ tính
Accounting (Banker's)	Mỗi thao tác "trả thêm" để dự trữ cho thao tác đắt	Khi muốn bound per-operation
Potential	Định nghĩa hàm thế năng $\mathrm{\Phi }$, chi phí amortized = chi phí thực + $\mathrm{\Delta }\mathrm{\Phi }$	Chặt chẽ nhất, dùng trong chứng minh

Best, Worst, Average Case

Một thuật toán có thể có complexity khác nhau tùy đầu vào:

Thuật toán	Best Case	Average Case	Worst Case
Quick Sort	$O(N\log N)$	$O(N\log N)$	$O(N^2)$ — pivot tệ
Binary Search	$O(1)$ — tìm ngay giữa	$O(\log N)$	$O(\log N)$
Hash Table lookup	$O(1)$	$O(1)$	$O(N)$ — nhiều collision
Insertion Sort	$O(N)$ — đã sắp xếp	$O(N^2)$	$O(N^2)$

Trong production, hãy thiết kế cho worst-case nhưng optimize cho average-case. Quick Sort trung bình nhanh hơn Merge Sort nhờ cache locality tốt hơn, dù worst-case tệ hơn — và randomized pivot gần như loại bỏ worst-case trong thực tế.

Thực chiến

Tình huống 1: Phát hiện truy vấn chậm bằng phân tích complexity

Bạn nhận ticket: "API endpoint /api/orders/duplicates timeout sau 30 giây khi có nhiều đơn hàng". Code hiện tại dùng thuật toán so sánh mọi cặp — $O(N^2)$.

C++ — O(N²) → O(N)

#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

struct Order {
    std::string id;
    std::string customerEmail;
    double amount;
    long timestamp;
};

// ❌ BẢN CŨ: O(N²) — so sánh mọi cặp
std::vector<std::pair<Order, Order>> findDuplicatesSlow(
    const std::vector<Order>& orders
) {
    std::vector<std::pair<Order, Order>> duplicates;
    for (size_t i = 0; i < orders.size(); ++i) {
        for (size_t j = i + 1; j < orders.size(); ++j) {
            if (orders[i].customerEmail == orders[j].customerEmail
                && orders[i].amount == orders[j].amount
                && std::abs(orders[i].timestamp - orders[j].timestamp) < 60) {
                duplicates.push_back({orders[i], orders[j]});
            }
        }
    }
    return duplicates; // N=50K → 1.25 tỷ so sánh → timeout
}

// ✅ BẢN MỚI: O(N log N) — nhóm theo key, chỉ so sánh trong nhóm
#include <unordered_map>

std::vector<std::pair<Order, Order>> findDuplicatesFast(
    std::vector<Order>& orders
) {
    // Bước 1: Nhóm theo (email, amount) — O(N)
    std::unordered_map<std::string, std::vector<size_t>> groups;
    for (size_t i = 0; i < orders.size(); ++i) {
        std::string key = orders[i].customerEmail + "|"
                        + std::to_string(orders[i].amount);
        groups[key].push_back(i);
    }

    // Bước 2: Trong mỗi nhóm, sort theo timestamp và so sánh liền kề
    std::vector<std::pair<Order, Order>> duplicates;
    for (auto& [key, indices] : groups) {
        if (indices.size() < 2) continue;
        std::sort(indices.begin(), indices.end(),
            [&](size_t a, size_t b) {
                return orders[a].timestamp < orders[b].timestamp;
            });
        for (size_t k = 1; k < indices.size(); ++k) {
            if (orders[indices[k]].timestamp
                - orders[indices[k-1]].timestamp < 60) {
                duplicates.push_back(
                    {orders[indices[k-1]], orders[indices[k]]});
            }
        }
    }
    return duplicates; // N=50K → vài nghìn so sánh → < 100ms
}

Python — O(N²) → O(N)

from dataclasses import dataclass
from collections import defaultdict
from itertools import pairwise

@dataclass
class Order:
    id: str
    customer_email: str
    amount: float
    timestamp: int

# ❌ BẢN CŨ: O(N²)
def find_duplicates_slow(orders: list[Order]) -> list[tuple[Order, Order]]:
    duplicates = []
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            if (orders[i].customer_email == orders[j].customer_email
                and orders[i].amount == orders[j].amount
                and abs(orders[i].timestamp - orders[j].timestamp) < 60):
                duplicates.append((orders[i], orders[j]))
    return duplicates  # N=50K → timeout

# ✅ BẢN MỚI: O(N log N) — group + sort
def find_duplicates_fast(orders: list[Order]) -> list[tuple[Order, Order]]:
    # Nhóm theo (email, amount) — O(N)
    groups: dict[tuple, list[Order]] = defaultdict(list)
    for order in orders:
        key = (order.customer_email, order.amount)
        groups[key].append(order)

    duplicates = []
    for group in groups.values():
        if len(group) < 2:
            continue
        # Sort theo timestamp — O(K log K) trong mỗi nhóm
        group.sort(key=lambda o: o.timestamp)
        for prev, curr in pairwise(group):
            if curr.timestamp - prev.timestamp < 60:
                duplicates.append((prev, curr))

    return duplicates  # N=50K → < 100ms

Java — O(N²) → O(N)

import java.util.*;
import java.util.stream.*;

record Order(String id, String customerEmail, double amount, long timestamp) {}
record DuplicatePair(Order a, Order b) {}

public class DuplicateDetector {

    // ❌ BẢN CŨ: O(N²)
    static List<DuplicatePair> findDuplicatesSlow(List<Order> orders) {
        List<DuplicatePair> duplicates = new ArrayList<>();
        for (int i = 0; i < orders.size(); i++) {
            for (int j = i + 1; j < orders.size(); j++) {
                Order a = orders.get(i), b = orders.get(j);
                if (a.customerEmail().equals(b.customerEmail())
                    && a.amount() == b.amount()
                    && Math.abs(a.timestamp() - b.timestamp()) < 60) {
                    duplicates.add(new DuplicatePair(a, b));
                }
            }
        }
        return duplicates;
    }

    // ✅ BẢN MỚI: O(N log N)
    static List<DuplicatePair> findDuplicatesFast(List<Order> orders) {
        Map<String, List<Order>> groups = orders.stream()
            .collect(Collectors.groupingBy(
                o -> o.customerEmail() + "|" + o.amount()));

        List<DuplicatePair> duplicates = new ArrayList<>();
        for (List<Order> group : groups.values()) {
            if (group.size() < 2) continue;
            group.sort(Comparator.comparingLong(Order::timestamp));
            for (int i = 1; i < group.size(); i++) {
                if (group.get(i).timestamp() - group.get(i-1).timestamp() < 60) {
                    duplicates.add(new DuplicatePair(group.get(i-1), group.get(i)));
                }
            }
        }
        return duplicates;
    }
}

Go — O(N²) → O(N)

package main

import (
	"fmt"
	"sort"
)

type Order struct {
	ID            string
	CustomerEmail string
	Amount        float64
	Timestamp     int64
}

type DuplicatePair struct{ A, B Order }

// ✅ BẢN MỚI: O(N log N)
func findDuplicatesFast(orders []Order) []DuplicatePair {
	// Nhóm theo (email, amount) — O(N)
	type groupKey struct {
		Email  string
		Amount float64
	}
	groups := make(map[groupKey][]Order)
	for _, o := range orders {
		key := groupKey{o.CustomerEmail, o.Amount}
		groups[key] = append(groups[key], o)
	}

	var duplicates []DuplicatePair
	for _, group := range groups {
		if len(group) < 2 {
			continue
		}
		sort.Slice(group, func(i, j int) bool {
			return group[i].Timestamp < group[j].Timestamp
		})
		for i := 1; i < len(group); i++ {
			if group[i].Timestamp-group[i-1].Timestamp < 60 {
				duplicates = append(duplicates,
					DuplicatePair{group[i-1], group[i]})
			}
		}
	}
	return duplicates
}

Kết quả: Với N = 50.000 đơn hàng, bản cũ cần ~1,25 tỷ so sánh (timeout). Bản mới: grouping $O(N)$ + sort trong mỗi nhóm nhỏ ≈ vài nghìn so sánh. Thời gian phản hồi giảm từ 30+ giây xuống dưới 100ms.

Tình huống 2: Chọn cấu trúc dữ liệu theo ràng buộc complexity

Bạn cần hệ thống autocomplete cho thanh tìm kiếm: nhập prefix, trả về top-10 gợi ý. Dữ liệu: 500.000 từ khóa. Yêu cầu: phản hồi dưới 50ms mỗi keystroke.

Python — So sánh giải pháp

from typing import Optional

# Giải pháp 1: Brute force — O(N × L) mỗi query, L = avg length
def autocomplete_brute(words: list[str], prefix: str) -> list[str]:
    return sorted(
        (w for w in words if w.startswith(prefix)),
        key=len
    )[:10]
# N=500K, mỗi keystroke quét toàn bộ → ~50ms, chấp nhận được?
# Nhưng khi prefix ngắn (1-2 ký tự), hầu như mọi từ match → sort O(N log N)

# Giải pháp 2: Trie — O(P + K) mỗi query, P = prefix length, K = kết quả
class TrieNode:
    __slots__ = ('children', 'is_end', 'top_suggestions')
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_end: bool = False
        self.top_suggestions: list[str] = []  # Pre-computed top 10

class AutocompleteTrie:
    def __init__(self, words: list[str]):
        self.root = TrieNode()
        # Build: O(N × L) — chỉ chạy một lần khi khởi tạo
        for word in words:
            node = self.root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_end = True
        self._precompute_suggestions(self.root, "")

    def _precompute_suggestions(self, node: TrieNode, prefix: str):
        """DFS pre-compute top suggestions cho mỗi node."""
        results: list[str] = []
        if node.is_end:
            results.append(prefix)
        for char, child in sorted(node.children.items()):
            self._precompute_suggestions(child, prefix + char)
            results.extend(child.top_suggestions)
        node.top_suggestions = sorted(results, key=len)[:10]

    def search(self, prefix: str) -> list[str]:
        """O(P) — chỉ traverse prefix, trả về kết quả đã tính sẵn."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return node.top_suggestions

# Build 1 lần: ~2 giây cho 500K từ
# Query: < 1ms mỗi keystroke — 50x nhanh hơn brute force

Tiêu chí	Brute Force	Trie (pre-computed)
Build time	Không cần	$O(N\times L)$ — một lần
Query time	$O(N\times L)$	$O(P)$ — P = prefix length
Memory	$O(N\times L)$	$O(N\times L\times \mathrm{\Sigma })$ — lớn hơn
Phù hợp khi	N < 10K	N > 10K, yêu cầu latency thấp

Đánh đổi rõ ràng: Trie dùng nhiều bộ nhớ hơn đáng kể, nhưng đổi lại query gần như instant. Đây là minh họa sống động của Time-Space Tradeoff.

Sai lầm điển hình

Sai lầm 1: Bỏ qua hằng số — "O(N) luôn nhanh hơn O(N log N)"

❌ SAI

# "O(N) nên dùng counting sort cho mọi trường hợp"
def sort_ages(ages: list[int]) -> list[int]:
    # Counting sort O(N + K), K = range
    count = [0] * 200  # age 0-199
    for age in ages:
        count[age] += 1
    result = []
    for age, c in enumerate(count):
        result.extend([age] * c)
    return result

✅ ĐÚNG — Cân nhắc ngữ cảnh

# Counting sort chỉ tối ưu khi range K nhỏ so với N.
# Nếu sort 100 phần tử có giá trị 0..10^9 → K = 10^9 >> N
# → Dùng comparison sort O(N log N) nhanh hơn nhiều.
# Luôn phân tích CẢ hằng số và bản chất dữ liệu.
ages = [25, 30, 22, ...]  # K=200, N=10M → counting sort thắng
prices = [999.99, 0.01, ...]  # K rất lớn → comparison sort thắng

Tại sao mắc phải: Quá tập trung vào ký hiệu Big O mà quên rằng $O$ bỏ qua hằng số. $O(N)$ với hằng số 1000 chậm hơn $O(N\log N)$ với hằng số 2 khi $N<{10}^{300}$.

Sai lầm 2: Complexity ẩn trong thư viện chuẩn

❌ SAI

# "Mỗi lần gọi `in` chỉ O(1) thôi mà"
def has_duplicates(items: list[int]) -> bool:
    seen = []
    for item in items:
        if item in seen:  # ← O(N) cho list! Không phải O(1)
            return True
        seen.append(item)
    return False
# Tổng: O(N²) — vì `in` trên list là linear scan

✅ ĐÚNG — Dùng đúng cấu trúc dữ liệu

def has_duplicates(items: list[int]) -> bool:
    seen: set[int] = set()  # set dùng hash table → `in` là O(1) avg
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False
# Tổng: O(N)

Tại sao mắc phải: Không nắm complexity của các thao tác trên từng cấu trúc dữ liệu. in trên list là $O(N)$, trên set/dict là $O(1)$ trung bình. Tra bảng complexity trước khi dùng.

Sai lầm 3: Nhân complexity khi nên cộng

❌ SAI — Phân tích sai

# Đọc file O(N) rồi sort O(N log N)
# → Kết luận: O(N × N log N) = O(N² log N)  ← SAI!

✅ ĐÚNG

# Hai bước TUẦN TỰ: O(N) + O(N log N) = O(N log N)
# Chỉ NHÂN khi bước trong lồng bước ngoài:
#   for x in arr:         ← O(N)
#       for y in arr:     ← O(N) cho MỖI x
#   → O(N) × O(N) = O(N²)

Quy tắc: Tuần tự → cộng, lồng nhau → nhân. Lấy max khi cộng.

Sai lầm 4: Bỏ qua worst-case của hash table

❌ SAI

// "HashMap là O(1), yên tâm dùng cho mọi trường hợp"
Map<CustomKey, Value> cache = new HashMap<>();
// Nếu hashCode() của CustomKey trả về cùng giá trị cho mọi key
// → Tất cả key vào cùng bucket → lookup degrade thành O(N)

✅ ĐÚNG

// Implement hashCode() phân bố đều
// Java 8+: bucket chuyển từ LinkedList sang TreeMap khi > 8 phần tử
// → worst-case cải thiện từ O(N) thành O(log N)
// Nhưng vẫn phải đảm bảo hash function tốt
@Override
public int hashCode() {
    return Objects.hash(field1, field2, field3);
}

Tại sao mắc phải: Hash table $O(1)$ là average-case. Worst-case là $O(N)$. Trong production, hash collision có thể bị khai thác thành tấn công HashDoS. Một số ngôn ngữ (Python, Rust) dùng randomized hashing để chống lại.

Sai lầm 5: Đệ quy không nhận ra exponential

❌ SAI

# "Đệ quy Fibonacci đơn giản, chắc O(N)"
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
# Thực tế: O(2^N) — fib(50) cần ~10^15 phép tính → hàng ngày

✅ ĐÚNG — Memoization biến O(2^N) thành O(N)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
# O(N) time, O(N) space — mỗi giá trị chỉ tính một lần

Tại sao mắc phải: Cây đệ quy nhị phân trông "có vẻ" chia đôi giống binary search ($O(\log N)$), nhưng thực tế nó nhân đôi số nhánh ở mỗi tầng. Vẽ cây đệ quy ra giấy là cách nhanh nhất phát hiện.

Under the Hood

Kỹ thuật suy luận complexity bằng tay

Quy tắc 1 — Đếm vòng lặp: Mỗi vòng lặp chạy $N$ lần nhân với công việc bên trong.

for i in range(N):          # N lần
    for j in range(N):      # × N lần
        doWork()            # × O(1)
→ O(N²)

for i in range(N):          # N lần
    for j in range(i):      # trung bình N/2 lần
        doWork()
→ Tổng = N(N-1)/2 = O(N²)

Quy tắc 2 — Chia đôi mỗi bước → O(log N):

while n > 0:
    n = n // 2              # Chia đôi → log₂(N) bước
→ O(log N)

# Binary search, cây nhị phân cân bằng, exponentiation by squaring

Quy tắc 3 — Đệ quy → vẽ cây hoặc dùng Master Theorem.

Master Theorem — Công cụ giải recurrence

Với đệ quy dạng $T(N)=a\cdot T(N/b)+O(N^c)$:

Điều kiện	Kết quả	Ví dụ
${\log }_{b}a<c$	$T(N)=O(N^c)$	Công việc tập trung ở gốc
${\log }_{b}a=c$	$T(N)=O(N^c\log N)$	Công việc phân bố đều
${\log }_{b}a>c$	$T(N)=O(N^{{\log }_{b}a})$	Công việc tập trung ở lá

Áp dụng:

Thuật toán	Recurrence	a, b, c	Kết quả
Binary Search	$T(N)=T(N/2)+O(1)$	1, 2, 0	${\log }_{2}1=0=c$ → $O(\log N)$
Merge Sort	$T(N)=2T(N/2)+O(N)$	2, 2, 1	${\log }_{2}2=1=c$ → $O(N\log N)$
Karatsuba	$T(N)=3T(N/2)+O(N)$	3, 2, 1	${\log }_{2}3\approx 1.58>1$ → $O(N^{1.58})$
Strassen	$T(N)=7T(N/2)+O(N^2)$	7, 2, 2	${\log }_{2}7\approx 2.81>2$ → $O(N^{2.81})$

Tại sao cơ số logarit không quan trọng trong Big O

${\log }_{a}N=\frac{{\log }_{b}N}{{\log }_{b}a}$. Vì ${\log }_{b}a$ là hằng số, nên $O({\log }_{a}N)=O({\log }_{b}N)$. Trong ký hiệu Big O, ta viết $O(\log N)$ mà không cần chỉ rõ cơ số — hằng số bị hấp thụ.

Tuy nhiên, cơ số có ảnh hưởng đến hằng số thực tế. B-tree dùng branching factor lớn (hàng trăm) để giảm số lần truy cập đĩa, dù complexity vẫn là $O(\log N)$.

Bảng tham chiếu cấu trúc dữ liệu — Average Case

Cấu trúc	Access	Search	Insert	Delete	Space
Array	$O(1)$	$O(N)$	$O(N)$	$O(N)$	$O(N)$
Linked List	$O(N)$	$O(N)$	$O(1)$*	$O(1)$*	$O(N)$
Hash Table	—	$O(1)$	$O(1)$	$O(1)$	$O(N)$
BST (balanced)	—	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(N)$
Heap	—	$O(N)$	$O(\log N)$	$O(\log N)$	$O(N)$
Trie	—	$O(L)$	$O(L)$	$O(L)$	$O(\mathrm{\Sigma }\cdot N\cdot L)$

*Linked List insert/delete $O(1)$ khi đã có pointer tới node. Tìm node là $O(N)$.

Khi nào Big O không đủ

Big O là công cụ tuyệt vời nhưng không phải chân lý tuyệt đối:

• Cache locality: Array $O(N)$ scan thường nhanh hơn linked list $O(N)$ scan gấp 10-100x vì CPU cache.
• Hằng số lớn: Thuật toán Coppersmith–Winograd nhân ma trận $O(N^{2.376})$ nhưng hằng số lớn đến mức không ai dùng trong thực tế.
• Kích thước thực tế: Nếu $N$ luôn nhỏ (< 100), thuật toán $O(N^2)$ đơn giản có thể nhanh hơn thuật toán $O(N\log N)$ phức tạp.
• I/O bound vs CPU bound: Thuật toán $O(N)$ đọc đĩa có thể chậm hơn $O(N^2)$ chạy hoàn toàn trên RAM.

Hãy dùng Big O để loại bỏ giải pháp không khả thi, sau đó benchmark để chọn giải pháp tối ưu.

Checklist ghi nhớ

✅ Checklist triển khai

• [ ] Xác định complexity trước khi code, không phải sau khi thấy chậm
• [ ] Ước lượng $N$ thực tế trong production, nhân với complexity để kiểm tra khả thi
• [ ] Phân biệt tuần tự (cộng) và lồng nhau (nhân) khi tính complexity
• [ ] Tra bảng complexity của mọi thao tác trên cấu trúc dữ liệu đang dùng
• [ ] Cẩn thận in trên list ($O(N)$) vs in trên set/dict ($O(1)$)
• [ ] Vẽ cây đệ quy khi gặp hàm gọi chính nó — phát hiện exponential sớm
• [ ] Dùng Master Theorem cho recurrence dạng $T(N)=aT(N/b)+O(N^c)$
• [ ] Nhớ: cơ số logarit không ảnh hưởng Big O, nhưng ảnh hưởng hằng số thực tế
• [ ] Thiết kế cho worst-case, optimize cho average-case
• [ ] Amortized $O(1)$ không có nghĩa là mọi thao tác đều $O(1)$ — cẩn thận với latency-sensitive systems
• [ ] Đánh đổi Time-Space: caching/memoization tăng tốc nhưng tốn bộ nhớ
• [ ] Big O loại bỏ hằng số — khi $N$ nhỏ, hằng số quan trọng hơn lớp complexity
• [ ] Benchmark sau khi chọn thuật toán — cache locality và I/O pattern ảnh hưởng lớn
• [ ] Code review: nhìn thấy vòng lặp lồng nhau → ngay lập tức hỏi "N bao nhiêu?"

Bài tập luyện tập

Bài 1: Xác định complexity

🧠 Quiz

Cho đoạn code sau, xác định time complexity:

def mystery(arr: list[int]) -> int:
    n = len(arr)
    total = 0
    i = 1
    while i < n:
        for j in range(n):
            total += arr[j]
        i *= 2
    return total

A. $O(N)$B. $O(N\log N)$C. $O(N^2)$D. $O(N^2\log N)$

Đáp án & Giải thích

Đáp án: B — $O(N\log N)$

Phân tích:

• Vòng while: i bắt đầu từ 1, nhân đôi mỗi lần → chạy ${\log }_{2}N$ lần.
• Vòng for bên trong: luôn chạy đúng $N$ lần.
• Tổng: ${\log }_{2}N\times N=O(N\log N)$.

Điểm nhầm lẫn phổ biến: nhiều người thấy 2 vòng lặp lồng nhau và kết luận ngay $O(N^2)$. Cần phải đếm thực sự bao nhiêu lần vòng ngoài chạy — ở đây nó chạy $\log N$ lần, không phải $N$ lần.

Bài 2: Tối ưu complexity

🧠 Quiz

Cho bài toán: Tìm cặp phần tử trong mảng có tổng bằng target. Mảng chưa được sắp xếp.

Phương án A — Sort rồi two pointers: $O(N\log N)$ Phương án B — Hash set: $O(N)$ average, $O(N)$ space Phương án C — Brute force: $O(N^2)$

Trong trường hợp nào phương án A lại tốt hơn phương án B, dù B có complexity thấp hơn?

Đáp án & Giải thích

Phương án A tốt hơn B khi:

1. Bộ nhớ bị giới hạn: Hash set cần $O(N)$ bộ nhớ phụ. Nếu $N$ rất lớn và RAM hạn chế (embedded system, huge dataset), sort in-place + two pointers chỉ cần $O(1)$ bộ nhớ phụ (nếu cho phép modify mảng gốc).

2. Cần tìm TẤT CẢ các cặp, nhiều target: Sau khi sort một lần $O(N\log N)$, mỗi query hai con trỏ chỉ tốn $O(N)$. Với $Q$ query: sort approach = $O(N\log N+QN)$, hash approach = $O(QN)$ — tương đương, nhưng sort approach có cache locality tốt hơn.

3. Worst-case guarantee: Hash table worst-case là $O(N)$ per lookup (collision). Sort + two pointers worst-case vẫn là $O(N\log N)$ — deterministic và ổn định.

4. Dữ liệu gần sắp xếp sẵn: Nếu mảng gần sorted, Timsort (Python) chạy gần $O(N)$.

Bài học: Complexity thấp hơn trên giấy không luôn có nghĩa nhanh hơn trong thực tế. Luôn cân nhắc constraints cụ thể.

Bài 3: Amortized analysis

🧠 Quiz

Cho cấu trúc dữ liệu Stack hỗ trợ thao tác multipop(k) — pop $k$ phần tử cùng lúc. Worst-case của multipop(k) là $O(k)$.

Nếu thực hiện một chuỗi $N$ thao tác gồm cả push và multipop, amortized cost của mỗi thao tác là bao nhiêu?

A. $O(N)$B. $O(k)$C. $O(1)$D. $O(\sqrt{N})$

Đáp án & Giải thích

Đáp án: C — $O(1)$ amortized

Lý luận bằng phương pháp Aggregate:

• Mỗi phần tử chỉ được push một lần và pop nhiều nhất một lần.
• Trong $N$ thao tác, tổng số push $\le N$, nên tổng số pop (kể cả qua multipop) cũng $\le N$.
• Tổng chi phí tất cả thao tác $\le 2N$.
• Amortized cost = $2N/N=O(1)$.

Lý luận bằng phương pháp Accounting: "Trả trước" 2 đồng cho mỗi push — 1 đồng cho việc push, 1 đồng "gửi tiết kiệm" trên phần tử đó. Khi multipop xảy ra, mỗi phần tử bị pop đã có 1 đồng dự trữ, nên multipop "miễn phí". Tổng chi phí per operation = 2 = $O(1)$.

Liên kết học tiếp

📚 Bài liên quan

Nền tảng liên quan trong Penalgo:

• Thuật toán Sắp xếp — Áp dụng phân tích complexity cho Merge Sort, Quick Sort, Heap Sort
• Binary Search — Ví dụ kinh điển của $O(\log N)$
• Dynamic Programming — Khi memoization biến exponential thành polynomial
• Cấu trúc dữ liệu nâng cao — Segment Tree, Fenwick Tree và complexity của chúng

Từ khóa tra cứu: big o notation, time complexity, space complexity, amortized analysis, master theorem, asymptotic analysis, algorithm complexity, computational complexity

Tìm kiếm nhanh: #big-o · #complexity · #amortized · #master-theorem