Ký hiệu Big O là ký hiệu toán học được sử dụng để mô tả độ phức tạp của thuật toán hoặc hàm tính toán. Trong khoa học máy tính, nó được sử dụng để đo lường hiệu quả của một thuật toán, tức là lượng thời gian và/hoặc không gian mà việc triển khai nó sử dụng.
Ký hiệu Big O là một công cụ để đo lường độ phức tạp của các thuật toán, thường tính toán các trường hợp xấu nhất hoặc trường hợp tốt nhất, đó là lý do tại sao đôi khi nó được gọi là “Big Os” (hoặc Big Order). Tuy nhiên, ký hiệu Big O không đo lường chính xác bất kỳ thước đo độ phức tạp cụ thể nào mà chỉ là một công cụ để ước tính độ phức tạp.
Ký hiệu Big O đưa ra phép đo độ phức tạp về thời gian trong trường hợp xấu nhất và cung cấp dấu hiệu chung về mức độ dự kiến của thuật toán sẽ hoạt động tốt như thế nào về mặt thời gian và không gian. Bằng cách sử dụng ký hiệu Big O, người ta có thể xác định độ phức tạp về thời gian của một thuật toán nhất định, đưa ra dấu hiệu về cách thuật toán chạy khi kích thước đầu vào tăng lên.
Ký hiệu Big O được biểu thị bằng O(f(n)), trong đó f(n) là độ phức tạp về thời gian của thuật toán. Độ phức tạp thời gian phổ biến được biểu thị bằng ký hiệu Big O bao gồm O(1) cho độ phức tạp thời gian không đổi, O(log n) cho độ phức tạp thời gian logarit, O(n) cho độ phức tạp thời gian tuyến tính, O(n2) cho độ phức tạp thời gian bậc hai và O (2n) cho độ phức tạp thời gian theo cấp số nhân.
Ký hiệu Big O có thể được sử dụng để so sánh các thuật toán khác nhau, cho phép xác định thuật toán hiệu quả nhất cho một vấn đề nhất định. Bằng cách sử dụng ký hiệu Big O, người ta có thể xác định các thuật toán phù hợp nhất để giải quyết một số vấn đề nhất định trong khi tính đến tài nguyên và thời gian.
