Big O Notation

11.1 Định nghĩa của Big O

Nốt Big O là một khái niệm toán học, dùng để mô tả giới hạn trên của thời gian thực thi hoặc lượng tài nguyên tiêu thụ của thuật toán dựa trên 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 quy mô tốt như thế nào và hiệu suất của nó thay đổi ra sao khi khối lượng dữ liệu tăng lên.

Nốt Big O tập trung vào những khía cạnh đáng kể nhất của thuật toán, bỏ qua các hằng số và 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 nốt chính:

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

• Thời gian thực thi 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.
• Ví dụ: truy cập một phần tử của mảng bằng chỉ số.

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

• Thời gian thực thi của thuật toán tỷ lệ thuận với kích thước của dữ liệu đầu vào.
• Ví dụ: duyệt qua tất cả các phần tử trong mảng.

O(log n) — Độ phức tạp lôgarit:

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

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

• Thời gian thực thi của thuật toán phụ thuộc vào bình phương của kích thước của 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 thi của thuật toán tăng hàm mũ khi kích thước của dữ liệu đầu vào tăng lên.
• Ví dụ: giải quyết bài toán cái ba lô bằng cách thử mọi trường hợp.

Ghi chú. Bạn sẽ tìm hiểu chi tiết hơn về tìm kiếm nhị phân, sắp xếp nổi bọt và bài toán cái ba lô trong các bài giảng tiếp theo.

11.2 Giải thích nốt Big O

Cách giải thích và sử dụng nốt Big O?

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

So sánh thuật toán: Big O cho phép so sánh các thuật toán về mặt 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 một thuật toán với O(n^2) khi xử lý dữ liệu rất lớn.

Phân tích trường hợp xấu nhất: Big O thường được dùng để phân tích trường hợp xấu nhất của thời gian thực thi thuật toán, giúp đánh giá độ phức tạp tối đa của nó.

Bỏ qua các hằng số

Hãy xem xét các ví dụ về việc bỏ qua các hằng số và thành phần ít quan trọng:

Ví dụ 1. Xem xét hai hàm số:

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

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

Ví dụ 2. Xem xét hai hàm số:

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

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

11.3. So sánh thuật toán

1. So sánh thuật toán trên lượng dữ liệu rất lớn

Ví dụ 1:

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

Với giá trị nhỏ của n, thuật toán A có thể chạy nhanh hơn do các hằng số nhỏ, nhưng với giá trị lớn của n, thuật toán B sẽ nhanh hơn đáng kể, vì tốc độ tăng trưởng của nó là lôgarit, 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 là O(n).
• Thuật toán Y có độ phức tạp thời gian là O(1).

Thuật toán Y sẽ luôn nhanh hơn, bất kể kích thước của n là bao nhiêu, vì O(1) có nghĩa là thời gian thực thi 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 là 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à cho mỗi phần tử trong mảng, cần phải so sánh và có thể đổi chỗ 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 là 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ố bước cần thiết để tìm thấy một phần tử sẽ phụ thuộc lôgarit 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 cái có độ phức tạp thời gian là O(n^2), và cái kia là 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 chú ý.

• Thuật toán với O(n^2) sẽ thực hiện khoảng 100 000 000 phép tính 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 tính cho 10 000 phần tử.

Ví dụ 2:

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

• Với n = 10: 2^10 = 1024 phép tính.
• Với n = 20: 2^20 = 1 048 576 phép tính.

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

1

Опрос

Cấu trúc dữ liệu,  52 уровень,  4 лекция

недоступен

Cấu trúc dữ liệu

Cấu trúc dữ liệu

Открыть