Độ phức tạp thời gian trong Python là gì?
Đây là một bài viết về độ phức tạp của thời gian trong lập trình Python. Trong đó, chúng tôi khám phá ý nghĩa của độ phức tạp thời gian và cho thấy cùng một chương trình có thể hiệu quả hơn hoặc kém hơn đáng kể về mặt thời gian thực hiện tùy thuộc vào thuật toán được sử dụng Show Các chủ đề được đề cập
Độ phức tạp của thời gian là một chủ đề mà nhiều lập trình viên tự học chưa học Khoa học máy tính có xu hướng né tránh. Tuy nhiên, rất đáng để nỗ lực tìm hiểu ít nhất những điều cơ bản của chủ đề này vì nó sẽ cho phép bạn viết mã hiệu quả hơn nhiều Chủ đề về Độ phức tạp của thời gian trong lập trình thoạt đầu có vẻ hơi khó khăn với một số ký hiệu toán học không quen thuộc và các biểu đồ khác nhau được sử dụng để biểu thị thời gian hoàn thành thuật toán tăng lên như thế nào khi kích thước đầu vào của nó tăng lên Tuy nhiên
Bạn có thể hiểu rõ về độ phức tạp của thời gian bằng trực giác bằng cách nghiên cứu đồ thị của các hàm toán học khác nhau và chiều cao của đồ thị tăng lên như thế nào khi chúng ta di chuyển dọc theo trục x. Biểu đồ dưới đây cho thấy các loại hàm toán học khác nhau hoạt động như thế nào. Ý tưởng là thời gian thực hiện của các thuật toán có thể tăng theo kiểu tương tự với một trong các hàm loại này, tùy thuộc vào việc thực hiện nó. Mục tiêu của chúng tôi là viết các thuật toán hoạt động giống như các hàm phát triển chậm hơn và tránh các triển khai hoạt động giống như các hàm phát triển nhanh Có rất nhiều chi tiết mà bạn có thể xem xét về việc chúng tôi đang xem xét trường hợp tốt nhất, trường hợp xấu nhất, trường hợp trung bình, v.v., nhưng đó thường là chi tiết hơn mức bạn cần. Để đơn giản, hãy nói
Ký hiệu Big O là một cách để chỉ các loại tăng trưởng này
Sách được đề xuất để học thuật toán và cấu trúc dữ liệuXin lưu ý, với tư cách là Cộng tác viên của Amazon, tôi kiếm được từ các giao dịch mua đủ điều kiện Trong phần còn lại của bài viết này, thay vì tập trung vào lý thuyết chung về độ phức tạp của thời gian, chúng ta sẽ xem xét một thuật toán cụ thể đếm các phần tử phổ biến trong một danh sách Hãy nhìn vào biểu đồ này Bạn có thể thấy rõ ràng trên biểu đồ thời gian thực hiện của nó sử dụng pyplot từ matplotlib, một thư viện vẽ sơ đồ mạnh mẽ cho Python. Chi tiết về cách sử dụng pyplot dành cho một bài viết khác, nhưng bằng cách kiểm tra mã bên dưới, bạn có thể hiểu được cách thức hoạt động của nó. Đoạn mã sử dụng Ví dụ về độ phức tạp của thời gian Danh sách mã Python
Một số quan sát
Bài viết này nhằm cung cấp cho bạn trải nghiệm thực tế về cách làm việc với độ phức tạp về thời gian trong Python như một phần giới thiệu về chủ đề này. Độ phức tạp của thời gian là một chủ đề lớn và có rất nhiều tài nguyên có sẵn để giúp bạn học trực tuyến. Một nơi bạn có thể thực hành là trên các trang web như hackerrank và dự án euler, nơi cách tiếp cận “brute force” có thể đưa ra câu trả lời đúng, nhưng không đúng trong khung thời gian yêu cầu Độ phức tạp thời gian và Python ví dụ là gì?Một thuật toán được cho là có độ phức tạp về thời gian tuyến tính khi thời gian chạy tăng tối đa tuyến tính với kích thước của dữ liệu đầu vào . Đây là độ phức tạp thời gian tốt nhất có thể khi thuật toán phải kiểm tra tất cả các giá trị trong dữ liệu đầu vào. Ví dụ. cho giá trị trong dữ liệu. in(giá trị)
Độ phức tạp thời gian với ví dụ là gì?Vì vậy, nếu tính toán 10 phần tử mất 1 giây, tính toán 100 phần tử mất 2 giây, 1000 phần tử mất 3 giây, v.v. Khi sử dụng thuật toán chia để trị, chẳng hạn như tìm kiếm nhị phân, độ phức tạp về thời gian là O(log n) .
Độ phức tạp thời gian là gì?Trong khoa học máy tính, độ phức tạp về thời gian là độ phức tạp tính toán mô tả lượng thời gian máy tính cần để chạy một thuật toán .
Độ phức tạp về thời gian và độ phức tạp về không gian trong Python là gì?Độ phức tạp về thời gian là thời gian mà thuật toán sử dụng để thực hiện từng nhóm lệnh . Tốt hơn hết là chọn thuật toán hiệu quả nhất khi một vấn đề đơn giản có thể giải quyết bằng các phương pháp khác nhau. Độ phức tạp không gian thường được gọi là dung lượng bộ nhớ mà thuật toán sử dụng. |