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:
Stack, Queue và Priority Queue trong Java Phần 3: Priority Queue 1. Định nghĩa Priority Queue là gì? Priority Queue là một danh sách dạng biến thể của queue với thứ tự sắp xếp dựa trên mức độ ưu tiên của phần tử. Tức danh sách này có cấu trúc đưa vào và đưa ra giống queue, chỉ có một điểm khác là sau khi đưa vào thì nó sẽ đẩy phần tử mới vào vị trí phù hợp theo thứ tự giảm dần từ rear – có giá trị cao nhất, đến top – có giá trị thấp nhất. Nói một chút về giá trị ưu tiên (priority). Về mặt tổng quan, đó là một cách để sắp xếp công việc nào sẽ được thực hiện trước, công việc nào sẽ được thực hiện sau. Về mặt cụ thể, đây là chỉ số giúp cho ta biết được phần tử nào sẽ được đưa ra ngoài trước, phần tử nào sẽ được đưa ra ngoài sau. Theo quy tắc trong đây, giá trị nào được xem như là nhỏ nhất thì sẽ được thực hiện trước. (Lưu ý: Việc định giá trị của 1 phần tử lớn hay nhỏ không theo 1 công thức cụ thể, mà phụ thuộc vào từng bài toán khác nhau). ...