Ký hiệu Big O 101: Bí quyết để viết các thuật toán hiệu quả

Từ các thao tác mảng đơn giản đến các thuật toán sắp xếp phức tạp, hiểu về Ký hiệu Big O là rất quan trọng để xây dựng các giải pháp phần mềm hiệu suất cao.

1 - O(1)

Đây là ký hiệu thời gian hằng số. Thời gian chạy vẫn ổn định bất kể kích thước đầu vào. Ví dụ, truy cập một phần tử trong mảng bằng chỉ số và chèn/xóa một phần tử trong bảng băm.

2 - O(n)

Ký hiệu thời gian tuyến tính. Thời gian chạy tăng tỷ lệ thuận với kích thước đầu vào. Ví dụ, tìm phần tử lớn nhất hoặc nhỏ nhất trong một mảng chưa được sắp xếp.

3 - O(log n)

Ký hiệu thời gian logarit. Thời gian chạy tăng chậm khi đầu vào tăng. Ví dụ, tìm kiếm nhị phân trên một mảng đã sắp xếp và các thao tác trên cây tìm kiếm nhị phân cân bằng.

4 - O(n^2)

Ký hiệu thời gian bậc hai. Thời gian chạy tăng theo cấp số nhân với kích thước đầu vào. Ví dụ, các thuật toán sắp xếp đơn giản như sắp xếp nổi bọt, sắp xếp chèn và sắp xếp chọn.

5 - O(n^3)

Ký hiệu thời gian bậc ba. Thời gian chạy tăng nhanh chóng khi kích thước đầu vào tăng. Ví dụ, nhân hai ma trận dày đặc bằng thuật toán ngây thơ.

6 - O(n logn)

Ký hiệu thời gian tuyến tính-logarit. Đây là sự kết hợp giữa tăng trưởng tuyến tính và logarit. Ví dụ, các thuật toán sắp xếp hiệu quả như sắp xếp trộn, sắp xếp nhanh và sắp xếp đống.

7 - O(2^n)

Ký hiệu thời gian mũ. Thời gian chạy tăng gấp đôi với mỗi phần tử đầu vào mới. Ví dụ, các thuật toán đệ quy giải quyết vấn đề bằng cách chia chúng thành nhiều bài toán con.

8 - O(n!)

Ký hiệu thời gian giai thừa. Thời gian chạy tăng vọt với kích thước đầu vào. Ví dụ, các vấn đề tạo hoán vị.

9 - O(sqrt(n))

Ký hiệu thời gian căn bậc hai. Thời gian chạy tăng tương đối với căn bậc hai của đầu vào. Ví dụ, tìm kiếm trong một phạm vi như Sàng Eratosthenes để tìm tất cả các số nguyên tố lên đến n.

TÁC GIẢ

Về ABN Asia: AiUTOMATING PEOPLE, ABN Asia được thành lập từ năm 2012, là một công ty xuất phát từ học thuật, do những giảng viên, cựu du học sinh Hungary, Hà Lan, Nga, Đức, và Nhật Bản sáng lập. Chúng tôi chia sẻ đam mê chung và tầm nhìn vững chắc về công nghệ, mang đến sự đổi mới và chất lượng đỉnh cao cho khách hàng. Phương châm của chúng tôi là: Tốt hơn. Nhanh hơn. An toàn hơn. Trong nhiều trường hợp: Rẻ hơn.

Hãy liên hệ với chúng tôi khi Quý doanh nghiệp có các nhu cầu về dịch vụ công nghệ thông tin, tư vấn chuyển đổi số, tìm kiếm các giải pháp phần mềm phù hợp, hoặc nếu Quý doanh nghiệp có đấu thầu CNTT (RFP) để chúng tôi tham dự. Quý doanh nghiệp có thể liên hệ với chúng tôi qua địa chỉ email [email protected]. Chúng tôi sẵn lòng hỗ trợ với mọi nhu cầu công nghệ của Quý doanh nghiệp.

© ABN ASIA