GIẢI THÍCH MỘT SỐ DẠNG BIG O: O(LOGN) Đây là một độ phức tạp điển hình, có rất nhiều trong các dạng cấu trúc dữ liệu và giải thuật cơ bản. Nắm được cách tính độ phức tạp O(logn) của các thuật toán sẽ giúp bạn tự tin hơn được 50% trong hầu hết các dạng big O. Trước khi bắt đầu bài viết, mình muốn các bạn cần tìm hiểu qua về hai bài viết cũ của mình về Big O là gì và cách tính độ phức tạp của Big O cho hàm đệ quy. Bạn tham khảo qua hai bài viết sau:
Chuyện gì xảy ra khi bạn chạy một chương trình (Bài viết này chỉ dành cho các bạn học lập trình và mong muốn hiểu rõ hơn về cách chương trình của mình vận hành. Nếu bạn là người ngoại đạo và vẫn muốn tiếp tục xem, thì xin mời ) Về tổng quan, khi bạn chạy chương trình (program), chương trình sẽ được nạp vào trong bộ nhớ chính và chờ thực thi. Lúc này, chương trình được gọi là tiến trình (process). Process chờ một khoảng thời gian cho đến khi nó được lựa chọn vào trong processor để thực thi (quá trình lựa chọn gọi là short-term scheduler). Đây là quá trình sơ bộ, nhưng ở đây mình sẽ phân tích kỹ hơn một chút.