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:
Thuật toán Quick Sort Quick Sort là một thuật toán sắp xếp không còn xa lạ với chúng ta. Không khó để tìm các tài liệu về Quick Sort, nhưng khá khó để hiểu Quick Sort một cách tường tận. Trong bài viết này, mình sẽ phân tích thuật toán trên một cách chi tiết nhất nhé. Nào bắt đầu thôi! THUẬT TOÁN Cho một dãy số 9, -1, 0, 4, 7, 10, 6. Dùng thuật toán Quick Sort để sắp xếp dãy số trên. Sau khi sắp xếp, kết quả cho ra sẽ là -1, 0, 4, 6, 7, 9, 10 là một dãy số tăng dần. Gọi quickSort(arr, l, r) là hàm của thuật toán với 3 thành phần: arr: mảng chúng ta cần sắp xếp l, r: left và right, là hai con số xác định phần nào của mảng arr dùng để sắp xếp Để dễ hình dung hơn, ta có ví dụ thế này Cho arr là dãy số lúc nãy. Như hình trên, ta thấy rằng l = 4, r = 6. Lúc đấy ta sẽ gọi hàm lúc nãy là quickSort(arr, 4, 6), hàm này sẽ chỉ sắp xếp một phần của dãy số là 7, 10, 6. Sau khi gọi hàm này sắp xếp, ta sẽ thu được dãy như sau Trong quá trình tính toán thì l và r mớ...