Khám Phá Khái Niệm BigO trong Thuật Toán
Trong lĩnh vực khoa học máy tính và phát triển phần mềm, việc lập trình ra những dòng mã chất lượng là điều cần thiết. Để đạt được điều này, lập trình viên cần nắm vững những khái niệm cơ bản. Trong số đó, BigO là một khái niệm nền tảng mà mọi lập trình viên cần phải hiểu rõ trước khi bước vào thế giới của các cấu trúc giải thuật và dữ liệu. Hãy cùng tìm hiểu về BigO, cách tính toán và tầm quan trọng của nó trong lập trình.
BigO là gì?
BigO là thuật ngữ mô tả độ phức tạp của thuật toán, được sử dụng để đánh giá và phân tích tính tối ưu của một thuật toán dựa vào mức độ gia tăng của số lượng biến đầu vào.
Các dạng BigO phổ biến:
- O(n): Độ phức tạp thời gian tuyến tính (Linear time)
- O(1): Độ phức tạp thời gian hằng số (Constant time) - Thời gian không thay đổi theo kích thước của đầu vào. Ví dụ, dù có 100,000 phần tử hay chỉ 1 phần tử, kết quả vẫn giống nhau.
- O(logN): Giảm một nửa thời gian mỗi lần lặp.
- O(n²): Độ phức tạp thời gian của thuật toán có hai vòng lặp lồng nhau.
Sự khác nhau giữa BigO, Big Omega và Big Theta
Để hiểu rõ hơn về ba khái niệm này, chúng ta có thể xem xét như sau:
- BigO: Phân tích trường hợp xấu nhất.
- Big Omega: Phân tích trường hợp tốt nhất (best case).
- Big Theta: Phân tích cả trường hợp xấu nhất, tốt nhất và trung bình.
Ví dụ về thuật toán tìm kiếm tuyến tính
javascript
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}- Big-O (
O(n)):- Trường hợp xấu nhất: Chúng ta phải kiểm tra tất cả các phần tử trong mảng (O(n)).
- Big Omega (
Ω(1)):- Trường hợp tốt nhất: Chúng ta tìm thấy giá trị cần tìm trong một phép kiểm tra (Ω(1)).
- Big Theta (
Θ(n)):- Trường hợp trung bình: Thông thường, phần tử sẽ được tìm thấy ở giữa mảng, yêu cầu n/2 phép kiểm tra (Θ(n)).
Cách tính toán BigO
Chúng ta có thể tính toán BigO dựa trên các quy tắc sau:
Quy tắc 1: Luôn chọn trường hợp xấu nhất
Quy tắc 2: Loại bỏ các hằng số
Quy tắc 3: Các biến đầu vào khác nhau nên có các độ phức tạp khác nhau
Quy tắc 4: Loại bỏ các giá trị không chiếm ưu thế (non-dominant)
Bài tập thực tế
Ví dụ 1: Tính toán độ phức tạp cho biểu thức O(n² + 3x + 100 + x/2)
- Quy tắc 1: Trường hợp xấu nhất là n²
- Quy tắc 2: Loại bỏ hằng số 100
- Quy tắc 3: Có 1 đầu vào là x
- Quy tắc 4: Loại bỏ non-dominant: Loại bỏ 3x + x/2
=> Giá trị thực tế BigO là O(n²).
Điều gì tạo nên một đoạn code tốt?
- Dễ đọc (Readable)
- Dễ mở rộng (Scalable)
- Tốc độ thực thi (Speed)
- Tiết kiệm bộ nhớ (Memory)
Vocab (Từ vựng liên quan)
- arbitrary: Tuỳ ý
- steepest: Dốc đứng, tốn kém nhất
- pillar: Trụ cột, mũi nhọn
- tradeoff: Đánh đổi giữa tốc độ và bộ nhớ.
Liên kết hữu ích
#tag: #thuật_toán #cấu_trúc_dữ_liệu #bigO
source: viblo
