Tám chuyện công nghệ

  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ớ...

Tính toán big O cho hàm đệ quy Nếu bạn chưa hiểu big O là gì, hãy đọc bài trước: https://8techblog.blogspot.com/2020/05/tim-hieu-o-phuc-tap-thoi-gian-big-o-cho.html Việc tính toán big O là một việc làm cần thiết trong quá trình lập trình, đặc biệt là với thời buổi hiện nay, kích thước dữ liệu ngày càng lớn và phức tạp, ta cần phải lựa chọn thuật toán và viết code một cách thông minh để đạt hiệu quả. Trong bài viết trước thì mình đã giải thích cách tìm big O rồi phải không nhỉ? Tuy nhiên, đó chỉ là big O cho các lệnh code bình thường. Bạn đang tự hỏi mình lệnh “không bình thường” mình muốn nhắc đến ở đây là gì phải không? Mình nghĩ bạn cũng đã tự trả lời được cho mình khi đọc tiêu đề rồi đấy. Vâng, đó chính là đệ quy. Thật sự khó khi tính toán big O cho các hàm đệ quy, vì việc mà kiểm soát được số lần lặp lại của hàm là chuyện quá ư là khó khăn. Tất nhiên, phải có giải pháp thì mình mới viết bài này chứ nhỉ :D. Đúng rồi đấy, giải pháp này có thể giúp bạn tính được big O của một ...