MetoolzyBig O Cheat Sheet
Complexity Growth Chart
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Data Structure Operations
Each cell shows Average / Worst case complexity.
| Data Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1)/O(1) | O(n)/O(n) | O(n)/O(n) | O(n)/O(n) |
| Stack | O(n)/O(n) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) |
| Queue | O(n)/O(n) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) |
| Linked List | O(n)/O(n) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) |
| Hash Table | —/— | O(1)/O(n) | O(1)/O(n) | O(1)/O(n) |
| BST | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) |
| AVL Tree | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) |
| B-Tree | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) |
| Red-Black | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) |
Common Algorithms
| Algorithm | Time | Space |
|---|---|---|
| Binary Search | O(log n) | O(1) |
| BFS | O(V+E) | O(V) |
| DFS | O(V+E) | O(V) |
| Dijkstra | O((V+E)log V) | O(V) |
| Bellman-Ford | O(VE) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
Interactive Chart
Hover over the growth chart to compare operations at any input size.
Common Complexities
O(1) to O(n!) — all major complexity classes with color-coded badges.
Code Examples
Sorting algorithms, data structures, and graph algorithms at a glance.
Comparison
Side-by-side tables for best, average, worst case and space complexity.
Giới thiệu về Big O Cheat Sheet
The Big O Notation Cheat Sheet is a comprehensive reference for algorithm and data structure time and space complexity. Big O notation describes how an algorithm's performance scales with input size — understanding it is essential for writing efficient code, passing technical interviews, and making informed architectural decisions. This tool provides an interactive growth chart where you can hover to compare how many operations different complexity classes require at any input size, plus reference tables for 9 sorting algorithms, 9 data structures, and 6 common graph and search algorithms. Each entry shows best, average, and worst-case time complexity and space complexity with colour-coded badges from green (efficient O(1), O(log n)) to red (avoid O(n²), O(2ⁿ)). Stability of sorting algorithms is also noted.
Làm sao để Big O Cheat Sheet?
- Hover over the Complexity Growth Chart to see the exact operation count for each complexity class at a given input size n.
- Study the colour coding: green = fast (O(1), O(log n)), yellow = acceptable (O(n)), orange = moderate (O(n log n)), red = slow (O(n²), O(2ⁿ)).
- Use the Sorting Algorithms table to compare sorting choices — remember Quick Sort has O(n²) worst case while Merge Sort guarantees O(n log n).
- Use the Data Structures table to choose the right structure — Hash Tables give O(1) average search but O(n) worst case; AVL Trees guarantee O(log n) for all operations.
- Check the Common Algorithms section for standard graph algorithm complexities (BFS, DFS, Dijkstra, Floyd-Warshall).
- Use the Stable column when selecting a sort for data where the order of equal elements matters.
Câu hỏi thường gặp
What is Big O notation and why does it matter?
Big O notation describes the upper bound of how an algorithm's runtime or memory usage grows as the input size n increases. It matters because an algorithm that works fine for 100 items may be completely unusable for 1,000,000 items. O(n²) at n=1000 means 1,000,000 operations; O(n log n) at n=1,000,000 means only ~20,000,000 — a 50× difference that becomes billions× at larger scales.
What is the difference between time complexity and space complexity?
Time complexity measures how the number of operations grows with input size. Space complexity measures how much extra memory the algorithm needs. For example, Merge Sort has O(n log n) time but O(n) space because it needs a temporary copy of the array. In-place algorithms like Heap Sort use O(1) extra space at the cost of more complex implementation.
Why does Hash Table have O(n) worst-case search?
Hash Tables achieve O(1) average search because keys are distributed across buckets using a hash function. In the worst case (a very poor hash function or many hash collisions), all keys end up in the same bucket, degenerating into a linked list with O(n) search. Good hash functions and load factor management (rehashing) keep the average near O(1).
When should I choose Merge Sort over Quick Sort?
Choose Merge Sort when: (1) you need guaranteed O(n log n) worst-case performance and cannot afford the O(n²) worst case of Quick Sort on sorted or adversarially chosen input, (2) you need a stable sort, or (3) you are sorting linked lists where random access is expensive. Choose Quick Sort when average performance matters more and you want in-place sorting with low cache miss rates.
What is amortized complexity and how does it relate to Big O?
Amortized complexity describes the average cost per operation over a sequence of operations, even if individual operations occasionally take longer. For example, dynamic arrays (like JavaScript arrays or Python lists) have O(1) amortized push even though they occasionally need O(n) to resize and copy — because resizes happen infrequently enough that the average cost per push is still O(1).
Cẩm Nang Tra Cứu Độ Phức Tạp Thuật Toán Big-O Cho Lập Trình Viên
Trong thực tế phát triển phần mềm và tối ưu website, việc sử dụng công cụ thuật toán big o đóng vai trò vô cùng quan trọng. Viết một đoạn code chạy được là bước khởi đầu, nhưng viết một giải thuật tối ưu có khả năng mở rộng khi dữ liệu tăng từ 1.000 lên 10.000.000 bản ghi mới là thước đo đẳng cấp của một kỹ sư phần mềm thực thụ. Trong khoa học máy tính, ký hiệu Big-O là ngôn ngữ tiêu chuẩn chung để đánh giá hiệu năng thuật toán. Bảng tra cứu độ phức tạp Big-O trực tuyến của Metoolzy cung cấp hệ thống cheat sheet trực quan, toàn diện về thời gian (Time Complexity) và không gian bộ nhớ (Space Complexity) cho tất cả các cấu trúc dữ liệu và thuật toán phổ biến nhất.
Khái Niệm Ký Hiệu Big-O (Big-O Notation) Là Gì?
Ký hiệu Big-O đại diện cho giới hạn trên (Upper Bound) của thời gian thực thi hoặc lượng bộ nhớ mà một thuật toán tiêu thụ khi kích thước đầu vào ($n$) tiến dần tới vô cùng. Thay vì đo bằng mili-giây (vốn phụ thuộc vào cấu hình phần cứng của từng máy tính), Big-O đo lường số lượng bước thực hiện tương quan với độ lớn của dữ liệu.
Các cấp độ phức tạp phổ biến từ tối ưu nhất đến kém hiệu quả nhất:
- $O(1)$ - Constant Time (Thời gian hằng số): Tốc độ tối ưu tuyệt đối. Thời gian thực thi không đổi dù dữ liệu có 1 hay 1 tỷ phần tử (ví dụ: truy cập mảng theo chỉ mục
arr[0], lấy giá trị trong Hash Table). - $O(\log n)$ - Logarithmic Time (Thời gian logarit): Hiệu năng xuất sắc. Mỗi bước thực hiện giảm đi một nửa không gian tìm kiếm (ví dụ: Tìm kiếm nhị phân - Binary Search).
- $O(n)$ - Linear Time (Thời gian tuyến tính): Thời gian tỷ lệ thuận trực tiếp với số phần tử đầu vào (ví dụ: Duyệt vòng lặp
forđơn qua danh sách). - $O(n \log n)$ - Linearithmic Time: Hiệu năng chuẩn mực của các thuật toán sắp xếp so sánh tối ưu (ví dụ: Merge Sort, Quick Sort trung bình, Heap Sort).
- $O(n^2)$ - Quadratic Time (Thời gian bậc hai): Hiệu năng kém với dữ liệu lớn. Thường xuất hiện khi có hai vòng lặp lồng nhau (ví dụ: Bubble Sort, Selection Sort, duyệt ma trận).
- $O(2^n)$ - Exponential Time (Thời gian mũ): Thuật toán bùng nổ thời gian cực nhanh, thường gặp trong các bài toán đệ quy ngây thơ như tính số Fibonacci không memoization.
- $O(n!)$ - Factorial Time (Thời gian giai thừa): Cực kỳ chậm chạp, chỉ khả thi với $n < 15$ (ví dụ: Bài toán Người du lịch - TSP bằng vét cạn).
Bảng Tra Cứu Độ Phức Tạp Các Cấu Trúc Dữ Liệu Phổ Biến
Dưới đây là bảng tổng hợp chi tiết về thời gian thực hiện các thao tác cơ bản:
| Cấu trúc dữ liệu | Truy cập (Access) | Tìm kiếm (Search) | Chèn (Insertion) | Xóa (Deletion) | Không gian (Space) |
|---|---|---|---|---|---|
| Mảng (Array) | $O(1)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Bảng băm (Hash Table) | $O(1)$ (N/A) | $O(1)$ | $O(1)$ | $O(1)$ | $O(n)$ |
| Danh sách liên kết đơn (Linked List) | $O(n)$ | $O(n)$ | $O(1)$ (đầu danh sách) | $O(1)$ | $O(n)$ |
| Ngăn xếp (Stack) | $O(n)$ | $O(n)$ | $O(1)$ (Push) | $O(1)$ (Pop) | $O(n)$ |
| Hàng đợi (Queue) | $O(n)$ | $O(n)$ | $O(1)$ (Enqueue) | $O(1)$ (Dequeue) | $O(n)$ |
| Cây tìm kiếm nhị phân (BST) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
| Cây tự cân bằng (AVL Tree / Red-Black) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
Bảng Tra Cứu Các Thuật Toán Sắp Xếp (Sorting Algorithms)
| Thuật toán sắp xếp | Trường hợp tốt nhất | Trường hợp trung bình | Trường hợp xấu nhất | Bộ nhớ phụ (Space) | Ổn định (Stable) |
|---|---|---|---|---|---|
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ (chọn pivot xấu) | $O(\log n)$ | Không |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Có |
| Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Không |
| Insertion Sort | $O(n)$ (đã sắp xếp) | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Có |
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Có |
| Counting Sort | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | Có |
Ứng Dụng Thực Tiễn Của Big-O Trong Thiết Kế Hệ Thống Và Phỏng Vấn Tuyển Dụng
- Chuẩn bị phỏng vấn Coding Interview (LeetCode, FAANG): Mọi câu hỏi phỏng vấn thuật toán tại các tập đoàn công nghệ lớn luôn kết thúc bằng câu hỏi kinh điển: "What is the time and space complexity of your solution, and can you optimize it?". Nắm vững bảng tra cứu Big-O giúp bạn tự tin giải thích và cải tiến giải thuật.
- Lựa chọn cấu trúc dữ liệu phù hợp trong dự án thực tế:
- Cần tra cứu dữ liệu theo ID liên tục với tần suất cao? Chọn ngay Hash Map / Object ($O(1)$).
- Cần thao tác chèn/xóa phần tử ở đầu mảng liên tục? Thay vì dùng
Array.unshift()trong JavaScript ($O(n)$), hãy sử dụng Linked List hoặc Double-ended Queue ($O(1)$).
- Phát hiện nút thắt cổ chai (Performance Bottlenecks): Một truy vấn database chứa vòng lặp lồng nhau (vấn đề $N+1$ query) sẽ biến hệ thống của bạn thành cấp số nhân $O(n^2)$, dẫn đến sập server khi có lượng truy cập tăng vọt.
Câu Hỏi Thường Gặp (FAQ)
Tại sao Quick Sort có trường hợp xấu nhất là $O(n^2)$ nhưng vẫn được ưa chuộng hơn Merge Sort?
Quick Sort hoạt động trực tiếp tại chỗ (In-place) với bộ nhớ phụ chỉ $O(\log n)$ và có hệ số hằng số ẩn (Hidden constant factor) rất nhỏ, tận dụng tối đa bộ nhớ đệm CPU Cache. Ngược lại, Merge Sort đòi hỏi cấp phát thêm một mảng phụ $O(n)$. Trong thực tế, các biến thể Quick Sort hiện đại (Dual-Pivot Quicksort) hầu như không bao giờ rơi vào trường hợp xấu nhất.
Độ phức tạp không gian (Space Complexity) có tính dung lượng của dữ liệu đầu vào không?
Không. Độ phức tạp không gian phụ trợ (Auxiliary Space Complexity) chỉ tính toán lượng bộ nhớ bổ sung mà thuật toán cần cấp phát thêm trong quá trình tính toán, không tính bộ nhớ đã cấp phát cho dữ liệu đầu vào ban đầu.
Sự khác biệt giữa Big-O ($O$), Big-Omega ($\Omega$) và Big-Theta ($\Theta$) là gì?
- Big-O ($O$): Giới hạn trên (Trường hợp xấu nhất - Worst case).
- Big-Omega ($\Omega$): Giới hạn dưới (Trường hợp tốt nhất - Best case).
- Big-Theta ($\Theta$): Giới hạn chặt chẽ cả trên và dưới (Trường hợp trung bình hoặc khi cận trên trùng cận dưới). Trong giao tiếp kỹ thuật hàng ngày, lập trình viên thường dùng thuật ngữ Big-O để bao hàm cả phân tích trường hợp xấu nhất và trung bình.
Tóm Tắt Lợi Ích Của Công Cụ
Việc áp dụng giải pháp thuật toán big o giúp bạn tiết kiệm đáng kể thời gian thao tác, loại bỏ sai sót thủ công và nâng cao năng suất làm việc mỗi ngày. Hãy thường xuyên thực hiện thuật toán big o trực tiếp trên Metoolzy để đạt hiệu quả tối ưu nhất cho dự án của bạn.
Công Cụ Liên Quan Hữu Ích Trên Metoolzy
Để nâng cao tối đa hiệu suất làm việc, bạn có thể kết hợp cùng các công cụ miễn phí sau:
- Algorithm Visualizer: Hỗ trợ mô phỏng thuật toán trực quan.
- Code Snippet Manager: Hỗ trợ quản lý đoạn mã lập trình.
Tóm Tắt Lợi Ích Của Công Cụ
Việc áp dụng giải pháp thuật toán big o giúp bạn tiết kiệm đáng kể thời gian thao tác, loại bỏ sai sót thủ công và nâng cao năng suất làm việc mỗi ngày. Hãy thường xuyên thực hiện thuật toán big o trực tiếp trên Metoolzy để đạt hiệu quả tối ưu nhất cho dự án của bạn. Nhờ khả năng xử lý tức thì, tính năng thuật toán big o sẽ là trợ thủ đắc lực không thể thiếu trong quy trình làm việc chuyên nghiệp.
📚 Bài Viết Cùng Chủ Đề Nên Đọc
- Code Playground Online: Trình Biên Tập Code HTML CSS JS: Chạy thử nghiệm thuật toán trực tuyến tức thì.
- Quy Chuẩn Viết & Format Câu Lệnh SQL Clean Code: Quy chuẩn viết truy vấn cơ sở dữ liệu tối ưu.