Ký hiệu Big O: Các khái niệm cơ bản

2.1 Định nghĩa ký hiệu Big O.

Ký hiệu Big O — là một ký hiệu toán học, được sử dụng để mô tả giới hạn trên cùng của thời gian thực hiện hoặc tài nguyên tiêu thụ của một thuật toán dựa vào kích thước của dữ liệu đầu vào. Nó giúp xác định, cách thuật toán mở rộng tốt và hiệu suất của nó thay đổi khi tăng lượng dữ liệu.

Ký hiệu Big O tập trung vào các khía cạnh quan trọng nhất của thuật toán, bỏ qua các hằng số và các thành phần ít quan trọng hơn, cho phép tập trung vào hành vi dài hạn của thuật toán.

Các ký hiệu cơ bản:

O(1) — Độ phức tạp hằng số:

• Thời gian thực hiện của thuật toán không phụ thuộc vào kích thước dữ liệu đầu vào.
• Ví dụ: truy cập phần tử của một mảng theo chỉ số.

O(n) — Độ phức tạp tuyến tính:

• Thời gian thực hiện của thuật toán thay đổi tuyến tính theo kích thước dữ liệu đầu vào.
• Ví dụ: duyệt qua tất cả các phần tử của một mảng.

O(log n) — Độ phức tạp logarit:

• Thời gian thực hiện của thuật toán tăng logarit khi kích thước dữ liệu đầu vào tăng.
• Ví dụ: tìm kiếm nhị phân trong một mảng đã được sắp xếp.

O(n^2) — Độ phức tạp bình phương:

• Thời gian thực hiện của thuật toán thay đổi bình phương theo kích thước dữ liệu đầu vào.
• Ví dụ: sắp xếp nổi bọt, sắp xếp chèn.

O(2^n) — Độ phức tạp hàm mũ:

• Thời gian thực hiện của thuật toán thay đổi hàm mũ theo kích thước dữ liệu đầu vào.
• Ví dụ: giải bài toán cái ba lô bằng cách thử toàn bộ.

2.2 Diễn giải ký hiệu Big O.

Làm thế nào để diễn giải và sử dụng ký hiệu Big O?

Bỏ qua các hằng số và thành phần ít quan trọng hơn:

Big O mô tả tăng trưởng của hàm, bỏ qua các hằng số và thành phần ít quan trọng hơn. Ví dụ, O(2n) và O(3n) được diễn giải là O(n).

So sánh các thuật toán:

Big O cho phép so sánh các thuật toán bằng hiệu quả tiệm cận của chúng. Ví dụ, một thuật toán với O(n log n) hiệu quả hơn so với một thuật toán với O(n^2) cho dữ liệu rất lớn.

Phân tích trường hợp xấu nhất:

Big O thường được sử dụng để phân tích trường hợp xấu nhất của thời gian thực hiện thuật toán, điều này cho phép đánh giá độ phức tạp tối đa của nó.

Bỏ qua các hằng số.

Bỏ qua các hằng số và thành phần ít quan trọng hơn

Ví dụ 1:

Xem xét hai hàm:

• f(n) = 3n + 2
• g(n) = 5n + 1

Cả hai hàm đều có độ phức tạp tuyến tính, vì thành phần chiếm ưu thế trong mỗi hàm là n. Do đó, cả hai hàm đều được diễn giải là O(n), mặc dù có sự khác biệt về hệ số và các thành phần phụ.

Ví dụ 2:

Xem xét hai hàm:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Cả hai hàm đều có độ phức tạp bình phương, vì thành phần chiếm ưu thế là n^2. Cả hai biểu thức được diễn giải là O(n^2), bất chấp sự khác biệt về các thành phần phụ và hệ số.

2.3. So sánh các thuật toán

1. So sánh các thuật toán trên dữ liệu có kích thước rất lớn

Ví dụ 1:

• Thuật toán A có độ phức tạp thời gian O(n^2).
• Thuật toán B có độ phức tạp thời gian O(n log n).

Đối với các giá trị nhỏ của n, thuật toán A có thể thực hiện nhanh hơn do hằng số nhỏ hơn, nhưng đối với các giá trị lớn của n, thuật toán B sẽ nhanh hơn đáng kể, vì sự tăng trưởng của nó là logarit chứ không phải là bình phương.

Ví dụ 2:

• Thuật toán X có độ phức tạp thời gian O(n).
• Thuật toán Y có độ phức tạp thời gian O(1).

Thuật toán Y sẽ luôn nhanh hơn, bất kể kích thước của n, vì O(1) nghĩa là thời gian thực hiện của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào.

2. Phân tích trường hợp xấu nhất

Ví dụ 1:

Thuật toán sắp xếp nổi bọt có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất, khi mảng được sắp xếp theo thứ tự ngược lại. Điều này có nghĩa là đối với mỗi phần tử trong mảng, cần so sánh và có thể trao đổi với mỗi phần tử khác.

Ví dụ 2:

Tìm kiếm nhị phân có độ phức tạp thời gian O(log n) trong trường hợp xấu nhất. Điều này có nghĩa là ngay cả trong trường hợp xấu nhất, số lượng bước cần thiết để tìm thấy phần tử sẽ phụ thuộc logarit vào kích thước của mảng, điều này rất hiệu quả.

3. Ảnh hưởng đến hiệu suất và khả năng mở rộng

Ví dụ 1:

Nếu chúng ta có hai thuật toán để xử lý dữ liệu, một với độ phức tạp thời gian O(n^2), và một với O(n log n), và chúng ta tăng kích thước dữ liệu từ 1000 phần tử lên 10,000 phần tử, sự khác biệt về hiệu suất sẽ rất đáng kể.

• Thuật toán với O(n^2) sẽ thực hiện khoảng 100,000,000 phép toán cho 10,000 phần tử.
• Thuật toán với O(n log n) sẽ thực hiện khoảng 40,000 phép toán cho 10,000 phần tử.

Ví dụ 2:

Hãy xem xét một thuật toán hoạt động với O(2^n). Nếu chúng ta tăng kích thước dữ liệu đầu vào từ 10 lên 20 phần tử, số lượng phép toán sẽ tăng theo cấp số nhân.

• Đối với n = 10: 2^10 = 1024 phép toán.
• Đối với n = 20: 2^20 = 1,048,576 phép toán.

Điều này cho thấy độ phức tạp hàm mũ trở nên không thực tế nhanh chóng đối với các giá trị n lớn.