Câu hỏi phỏng vấn Big-O Notation
Câu hỏi

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?

Câu trả lời
  1. O(1) - Hằng số:

    • Ví dụ: Truy xuất phần tử đầu tiên trong một mảng có kích thước cố định.
  2. O(log n) - Logarithmic:

    • Ví dụ: Tìm kiếm nhị phân trong một danh sách được sắp xếp.
  3. O(n) - Tuyến tính:

    • Ví dụ: Duyệt qua một mảng để tìm một phần tử cụ thể.
  4. O(n log n) - Linearithmic:

    • Ví dụ: Sắp xếp nhanh (Quick Sort).
  5. O(n²) - Bậc hai:

    • Ví dụ: Sắp xếp chọn (Selection Sort).
  6. O(2ⁿ) - Exponential:

    • ...
middle

middle

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

senior

Sự khác biệt giữa Lower BoundTight Bound là gì?

senior

Các thuật toán thông dụng hàng ngày mà có độ phức tạp là O(1), O(n log n), và O(log n) là gì?

junior

Trong thuật toán, điều gì được chỉ ra khi một thao tác có độ phức tạp là O(log n)?

Bình luận

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

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