Câu hỏi

Bạn biết gì về ký hiệu big-O (big-O notation) và bạn có thể cho biết một số ví dụ liên quan đến các cấu trúc dữ liệu khác nhau?

Câu trả lời

Ký hiệu Big-O (big-O notation) là một khái niệm được sử dụng trong lĩnh vực của phân tích thuật toán và hiệu suất của các cấu trúc dữ liệu. Nó mô tả cách thuật toán hoặc cấu trúc dữ liệu thay đổi khi kích thước đầu vào tăng lên.

Ký hiệu Big-O giúp chúng ta đánh giá hiệu suất của thuật toán hoặc cấu trúc dữ liệu trong trường hợp xấu nhất (worst-case), nghĩa là khi số lượng phần tử trong cấu trúc dữ liệu đạt đến giới hạn cao nhất. Nó cho biết tốc độ tăng của thời gian thực thi hay tiêu thụ bộ nhớ của thuật toán hoặc cấu trúc dữ liệu theo số lượng phần tử đầu vào.

Ví dụ, trong ký hiệu Big-O, O(1) đại diện cho thời gian thực thi không phụ thuộc vào số lượng phần tử, O(n) đại diện cho thời gian thực thi tuyến tính, O(n^2) đại diện cho thời gian thực thi bậc hai, và O(log n) đại diện cho thời gian thực thi theo logarithm cơ số 2 của số lượng phần tử.

Một số ví dụ về ký hiệu Big-O liên qu...

Bạn cần đăng nhập để xem
entry

entry

Gợi ý câu hỏi phỏng vấn

senior

Nếu một hoạt động có độ phức tạp là O(n!), điều đó có ý nghĩa gì?

junior

Giải thích sự khác biệt giữa độ phức tạp không gian O(1)O(n)?

middle

Liệt kê một số loại độ phức tạp Big O và ví dụ về thuật toán tương ứng?

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào