Độ phức tạp thuật toán (Big-O)

Độ phức tạp thời gian và không gian của thuật toán và cấu trúc dữ liệu thông dụng. Gợi ý: với mỗi thẻ, tự giải thích vì sao ra kết quả đó.

Tạo bởi Thư viện Flashcard

Lập trình#big-o#giải thuật47 thẻTiếng ViệtCC BY 4.0Phiên bản 1 · 19 thg 11, 2026

Xem trước thẻ

  • Mặt trước

    Big-O dùng để làm gì?

    Mặt sau

    Mô tả cận trên tốc độ tăng của thời gian (hoặc bộ nhớ) theo kích thước đầu vào n khi n lớn.

  • Mặt trước

    O(1) nghĩa là gì?

    Mặt sau

    Thời gian hằng số, không phụ thuộc n.

  • Mặt trước

    O(log n) nghĩa là gì?

    Mặt sau

    Tăng rất chậm; mỗi bước giảm bài toán đi một phần (thường một nửa).

  • Mặt trước

    O(n) nghĩa là gì?

    Mặt sau

    Thời gian tăng tuyến tính theo n.

  • Mặt trước

    O(n log n) thường gặp ở đâu?

    Mặt sau

    Các thuật toán sắp xếp so sánh hiệu quả như merge sort, heap sort, quick sort (trung bình).

  • Mặt trước

    O(n²) thường gặp ở đâu?

    Mặt sau

    Hai vòng lặp lồng nhau cùng chạy theo n, ví dụ bubble sort, insertion sort xấu nhất.

  • Mặt trước

    O(2^n) thường gặp ở đâu?

    Mặt sau

    Đệ quy phân nhánh kép không nhớ, ví dụ Fibonacci đệ quy ngây thơ, liệt kê mọi tập con.

  • Mặt trước

    O(n!) thường gặp ở đâu?

    Mặt sau

    Liệt kê mọi hoán vị, ví dụ giải Người bán hàng bằng vét cạn.

  • Mặt trước

    Sắp xếp các độ phức tạp từ nhanh đến chậm khi n lớn?

    Mặt sau

    O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!).

  • Mặt trước

    Vì sao bỏ hằng số và số hạng bậc thấp trong Big-O?

    Mặt sau

    Khi n rất lớn, số hạng bậc cao nhất quyết định tốc độ tăng. O(3n + 10) viết là O(n).

và 37 thẻ khác