Giới thiệu

Sắp xếp là thao tác sắp xếp một chuỗi bản ghi theo thứ tự tăng dần hoặc giảm dần dựa trên giá trị của một hoặc một số key trong đó. Thuật toán sắp xếp là phương pháp sắp xếp các bản ghi theo yêu cầu. Thuật toán sắp xếp được coi trọng trong nhiều lĩnh vực, đặc biệt là xử lý lượng dữ liệu lớn. Một thuật toán tốt có thể tiết kiệm rất nhiều tài nguyên. Để có được một thuật toán tốt và phù hợp với thực tế, cần xem xét các ràng buộc và quy tắc khác nhau của dữ liệu trong từng lĩnh vực, đồng thời phải trải qua nhiều suy luận và phân tích.

Dãy Fibonacci

Mô tả bài toán:

Mọi người đều biết dãy Fibonacci. Bây giờ yêu cầu nhập một số nguyên n và xuất phần tử thứ n của dãy Fibonacci. n<=39

Phân tích vấn đề:

Có thể khẳng định bài này chắc chắn giải được bằng đệ quy, nhưng cách này có một vấn đề lớn: việc tính toán trùng lặp quá nhiều khi đệ quy sẽ gây tràn bộ nhớ. Ngoài ra có thể dùng phương pháp lặp, lưu kết quả trong quá trình tính bằng fn1 và fn2 rồi tái sử dụng. Dưới đây là code ví dụ của cả hai phương pháp và so sánh thời gian chạy của chúng.