HomeLập trìnhPythonGiải thích về...

Giải thích về Ghi nhớ, Đệ quy và Vòng lặp For trong Python


Có nhiều hơn một cách để làm mọi việc. Luôn có những quan điểm và phong cách quảng cáo chiêu hàng khác nhau. ~Tim Hudson

Trong bài viết này, chúng ta sẽ sử dụng ba kỹ thuật khác nhau trong Python để viết mã một chương trình Fibonacci cơ bản, kết quả là sẽ đưa ra tổng của chuỗi. Dãy Fibonacci là 0,1,1,2,3,5,8…

Như bạn có thể nhận thấy, chúng ta cộng số thứ nhất và số thứ hai, 0 và 1, để được số thứ ba trong dãy (1) -> 0+1=1. Sau đó, chúng tôi cộng các số thứ hai và thứ ba, 1+1=2, để có được số thứ 4 trong dãy…v.v.

Bạn có thể triển khai mã này trong Jupyter, Colab hoặc bất kỳ IDE hay trình soạn thảo văn bản nào mà bạn cảm thấy thoải mái.

Cách mã hóa chuỗi Fibonacci bằng vòng lặp For trong Python

Ở đây, tôi đã viết một chương trình Fibonacci cơ bản sử dụng vòng lặp for trong Python. Logic đằng sau điều này rất đơn giản và chúng ta đã thảo luận về nó ở trên.

Độ phức tạp thời gian là O(N) và độ phức tạp không gian là O(1) hoặc hằng số. Nhưng, nó thực sự phức tạp hơn sự phức tạp này ngụ ý.

“Nếu số của bạn nhỏ hơn N < 94, và bạn sử dụng số nguyên 64 bit, thì thuật toán hoạt động như một độ phức tạp tuyến tính. Tuy nhiên, đối với N > 94 nó bắt đầu hoạt động giống như một thuật toán phức tạp bậc hai.” ~ Michael Veksler

máy chủCode_forR_1
In kết quả Fibonacci bằng Vòng lặp For

Tôi sẽ chạy cái này với Python’s %timeit mô-đun. Điều này tránh được một số bẫy phổ biến để đo thời gian thực hiện. Bạn có thể xem thêm công dụng tại đây.

Đọc thêm  Đăng nhập bằng Python – Cách sử dụng nhật ký để gỡ lỗi các dự án Django của bạn
mã máy chủ_choR_R_1
Phải mất 675 nanoSec trên mỗi vòng lặp cho 10

Cách mã hóa chuỗi Fibonacci bằng đệ quy trong Python

Ở đây, chúng tôi sẽ thực hiện trình tự bằng cách sử dụng đệ quy. Các hàm đệ quy có xu hướng tự gọi lặp lại cho đến khi chúng đạt đến trường hợp cơ sở. Vì vậy, đệ quy tạo ra một cấu trúc cây.

Nếu chúng ta lấy một chuỗi Fibonacci gồm 5, thì đây là cây sẽ được tạo bằng đệ quy.

serverCode_foR_R2_1

Độ phức tạp không gian là O(N) và độ phức tạp thời gian là O(2^N) vì nút gốc có 2 con và 4 cháu. Và, như bạn có thể thấy, mỗi nút có 2 nút con.

Bây giờ độ sâu là N, có nghĩa là chúng ta phải làm điều này N lần. Ngoài ra, bạn có thể nhận thấy rằng cây con bên phải nhỏ hơn cây con bên trái, vì vậy thời gian chạy thực là khoảng O(1,6^N).

Trường hợp cơ bản: Fibonacci(2) = sợi(1) + sợi(0) = 1 + 0 = 1

máy chủCode_Recur_op_2
In kết quả Fibonacci bằng Đệ quy

Ví dụ về Fibonacci đệ quy chắc chắn nhanh hơn vòng lặp for.

máy chủCode_Recur_R_2

Cách mã hóa chuỗi Fibonacci bằng cách sử dụng tính năng ghi nhớ trong Python

Ghi nhớ là một kỹ thuật có thể cải thiện đáng kể hiệu suất của hàm đệ quy bằng cách giảm trách nhiệm tính toán.

Nó lưu trữ kết quả của các lệnh gọi hàm đắt tiền trong một mảng hoặc từ điển và trả về kết quả được lưu trong bộ nhớ cache khi cùng một đầu vào được gọi.

Bạn có thể xem cây trên để tham khảo và cách một số đầu vào nhất định tiếp tục được tính toán lại trên mỗi cuộc gọi đến chúng.

Đọc thêm  Đối với vòng lặp trong Python
máy chủCode_Memo_op_3
In kết quả Fibonacci bằng Memoisation

Độ phức tạp thời gian là O(nlogn).

máy chủCode_Memo_R_3

Cái nào tốt hơn, đệ quy, vòng lặp for hay ghi nhớ?

Bây giờ, những kỹ thuật này không được cho là tốt hơn nhau. Bạn chỉ cần biết khi nào bạn cần sử dụng cái nào. Mà tất nhiên phụ thuộc vào yêu cầu của bạn.

Phép lặp sẽ nhanh hơn đệ quy vì đệ quy phải xử lý khung ngăn xếp lệnh gọi đệ quy. Tuy nhiên, nếu đệ quy được viết bằng ngôn ngữ tối ưu hóa lệnh gọi đuôi, thì nó sẽ loại bỏ chi phí hoạt động và gần như ngang bằng với các vòng lặp for.

Cuối cùng, ghi nhớ sẽ tốt hơn bất cứ khi nào không gian trạng thái thưa thớt, nghĩa là không phải tất cả các vấn đề con nhỏ hơn cần được giải quyết, mà chỉ một vài trong số chúng.

Cảm ơn vì đã đọc! Nếu bạn thích bài viết này, bạn có thể đọc các bài viết khác của tôi ở đây. Bạn có thể thể hiện sự đánh giá cao của bạn cho bài viết này bằng cách chia sẻ nó. Bạn cũng có thể kết nối với tôi trên LinkedIn.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status