Một vấn đề ví dụ điển hình để hiển thị các thuật toán với các bậc độ lớn khác nhau là vấn đề phát hiện đảo chữ cổ điển cho các chuỗi. Một chuỗi là đảo chữ của chuỗi khác nếu chuỗi thứ hai chỉ đơn giản là sự sắp xếp lại của chuỗi thứ nhất. Ví dụ, Show 3. 4. 1. Giải pháp 1. Kiểm tra tắtGiải pháp đầu tiên của chúng tôi cho vấn đề đảo chữ sẽ kiểm tra độ dài của các chuỗi và sau đó để xem mỗi ký tự trong chuỗi đầu tiên có thực sự xuất hiện trong chuỗi thứ hai hay không. Nếu có thể “đánh dấu” từng ký tự thì hai chuỗi phải là đảo chữ cái. Việc đánh dấu một ký tự sẽ được thực hiện bằng cách thay thế nó bằng giá trị Python đặc biệt Để phân tích thuật toán này, chúng ta cần lưu ý rằng mỗi ký tự trong số n ký tự trong \[\begin{split}\sum_{i=1}^{n} i &= \frac {n(n+1)}{2} \\ &= \frac {1}{2}n^{2 Khi \(n\) trở nên lớn, số hạng \(n^{2}\) sẽ lấn át số hạng \(n\) và \(\frac {1}{2}\) có thể bỏ qua. Do đó, giải pháp này là \(O(n^{2})\) 3. 4. 2. Giải pháp 2. Sắp xếp và so sánhMột giải pháp khác cho vấn đề đảo chữ sẽ sử dụng thực tế là mặc dù test = 0 for i in range(n): test = test + 1 for j in range(n): test = test - 12 tích hợp trên danh sách bằng cách chuyển đổi từng chuỗi thành danh sách ngay từ đầu Thoạt nhìn, bạn có thể nghĩ rằng thuật toán này là \(O(n)\), vì có một phép lặp đơn giản để so sánh n ký tự sau quá trình sắp xếp. Tuy nhiên, hai lệnh gọi phương thức test = 0 for i in range(n): test = test + 1 for j in range(n): test = test - 12 của Python không phải là không có chi phí riêng. Như chúng ta sẽ thấy trong chương sau, việc sắp xếp thường là \(O(n^{2})\) hoặc \(O(n\log n)\), do đó, thao tác sắp xếp chiếm ưu thế trong quá trình lặp. Cuối cùng, thuật toán này sẽ có cùng thứ tự độ lớn như của quá trình sắp xếp 3. 4. 3. Giải pháp 3. Lực lượng vũ phuMột kỹ thuật vũ phu để giải quyết vấn đề thường cố gắng làm cạn kiệt mọi khả năng. Đối với vấn đề phát hiện đảo chữ cái, chúng ta chỉ cần tạo một danh sách tất cả các chuỗi có thể sử dụng các ký tự từ Thì ra \(n. \) thậm chí còn tăng nhanh hơn \(2^{n}\) khi n lớn hơn. Trên thực tế, nếu 3. 4. 4. Giải pháp 4. Đếm và so sánhLời giải cuối cùng của chúng ta cho bài toán đảo chữ tận dụng thực tế là hai phép đảo chữ bất kỳ sẽ có cùng số chữ a, cùng số chữ b, cùng số chữ c, v.v. Để quyết định xem hai chuỗi có phải là đảo chữ cái hay không, trước tiên chúng ta sẽ đếm số lần mỗi ký tự xuất hiện. Vì có 26 ký tự có thể, chúng ta có thể sử dụng danh sách 26 bộ đếm, một bộ đếm cho mỗi ký tự có thể. Mỗi khi chúng ta nhìn thấy một ký tự cụ thể, chúng ta sẽ tăng bộ đếm tại vị trí đó. Cuối cùng, nếu hai danh sách bộ đếm giống hệt nhau, các chuỗi phải được đảo chữ cái. cho thấy giải pháp này Một lần nữa, giải pháp có một số lần lặp lại. Tuy nhiên, không giống như giải pháp đầu tiên, không có giải pháp nào được lồng vào nhau. Hai lần lặp đầu tiên được sử dụng để đếm các ký tự đều dựa trên n. Lần lặp thứ ba, so sánh hai danh sách đếm, luôn mất 26 bước vì có 26 ký tự có thể có trong chuỗi. Cộng tất cả sẽ cho chúng ta các bước \(T(n)=2n+26\). Đó là \(O(n)\). Chúng tôi đã tìm thấy một thứ tự tuyến tính của thuật toán độ lớn để giải quyết vấn đề này Trước khi rời khỏi ví dụ này, chúng ta cần nói điều gì đó về yêu cầu không gian. Mặc dù giải pháp cuối cùng có thể chạy trong thời gian tuyến tính, nhưng nó chỉ có thể làm như vậy bằng cách sử dụng bộ nhớ bổ sung để giữ hai danh sách đếm ký tự. Nói cách khác, thuật toán này đã hy sinh không gian để đạt được thời gian đây là trường hợp thường xảy ra. Trong nhiều trường hợp, bạn sẽ cần đưa ra quyết định giữa sự đánh đổi giữa thời gian và không gian. Trong trường hợp này, lượng không gian thêm không đáng kể. Tuy nhiên, nếu bảng chữ cái cơ bản có hàng triệu ký tự, sẽ có nhiều mối quan tâm hơn. Là một nhà khoa học máy tính, khi được lựa chọn thuật toán, bạn sẽ quyết định cách sử dụng tài nguyên máy tính tốt nhất cho một vấn đề cụ thể |
