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:
[Design Pattern] Phần 2: Observer Pattern Ở phần thứ nhất, ta đã nói về Strategy Pattern – một dạng pattern cho phép phân tách thuật toán ra khỏi tính kế thừa. Tại phần thứ hai, ta sẽ làm quen với Observer Pattern, một loại pattern xử lý vấn đề cập nhật thông tin Trước khi đi vào phần thiết kế, ta sẽ lấy một ví dụ để hiểu rõ hơn Observer Pattern là gì! Có ba đế quốc hùng mạnh trên thế giới là Clown, Immortality, và Death. Cả ba vương quốc này đều căm ghét nhau và muốn thống trị các bên còn lại. Đế quốc Clown đang phát triển vũ khí hủy diệt hàng loạt với sức công phá cực mạnh, làm cho hai đế quốc còn lại cảm thấy lo ngại. John là một tình báo viên với nhiệm vụ thu thập tin tức từ phe địch về cho phe ta. John ban đầu thuộc phe Immortality đi thu thập thông tin từ đế quốc Clown. Tuy nhiên anh hay tin rằng Death cũng muốn có được thông tin từ Clown. Vì John là một người không theo phe nào cả, chỉ đi theo lợi ích của anh ta, nên anh ta sẽ đi thu thập tin tức từ Clown và bán lại ...