Độ phức tạp về thời gian của tìm kiếm tuyến tính trong python
Thuật toán tìm kiếm là một khái niệm khoa học máy tính cơ bản mà bạn nên hiểu với tư cách là nhà phát triển. Chúng hoạt động bằng cách sử dụng phương pháp từng bước để định vị dữ liệu cụ thể trong tập hợp dữ liệu Show
Trong bài viết này, chúng ta sẽ tìm hiểu cách các thuật toán tìm kiếm hoạt động bằng cách xem xét cách triển khai của chúng trong Java và Python Thuật toán tìm kiếm là gì?Theo Wikipedia, một thuật toán tìm kiếm là Bất kỳ thuật toán nào giải quyết vấn đề tìm kiếm, cụ thể là truy xuất thông tin được lưu trữ trong một số cấu trúc dữ liệu hoặc được tính toán trong không gian tìm kiếm của miền vấn đề, với các giá trị rời rạc hoặc liên tục Các thuật toán tìm kiếm được thiết kế để kiểm tra hoặc truy xuất một phần tử từ bất kỳ cấu trúc dữ liệu nào mà phần tử đó đang được lưu trữ. Họ tìm kiếm mục tiêu (khóa) trong không gian tìm kiếm Các loại thuật toán tìm kiếmTrong bài đăng này, chúng ta sẽ thảo luận về hai loại thuật toán tìm kiếm quan trọng
Hãy thảo luận chi tiết về hai vấn đề này với các ví dụ, triển khai mã và phân tích độ phức tạp về thời gian Tìm kiếm tuyến tính hoặc tuần tựThuật toán này hoạt động bằng cách lặp lại tuần tự toàn bộ mảng hoặc danh sách từ một đầu cho đến khi tìm thấy phần tử đích. Nếu phần tử được tìm thấy, nó sẽ trả về chỉ mục của nó, ngược lại -1 Bây giờ hãy xem một ví dụ và cố gắng hiểu nó hoạt động như thế nào
Giả sử phần tử mục tiêu mà chúng tôi muốn tìm kiếm là 3Phương pháp tìm kiếm tuyến tính hoặc tuần tự
Triển khai mãBây giờ hãy xem cách chúng tôi triển khai loại thuật toán tìm kiếm này trong một vài ngôn ngữ lập trình khác nhau Tìm kiếm tuyến tính hoặc tuần tự trong Java
Tìm kiếm tuyến tính hoặc tuần tự trong Python
Phân tích độ phức tạp thời gianTrường hợp tốt nhất xảy ra khi phần tử đích là phần tử đầu tiên của mảng. Số lần so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp thời gian là 4Trường hợp trung bình. Trung bình, phần tử đích sẽ ở đâu đó ở giữa mảng. Số lần so sánh, trong trường hợp này, sẽ là N/2. Vì vậy, độ phức tạp của thời gian sẽ là 5 (hằng số bị bỏ qua)Trường hợp xấu nhất xảy ra khi phần tử đích là phần tử cuối cùng trong mảng hoặc không có trong mảng. Trong trường hợp này, chúng ta phải duyệt qua toàn bộ mảng và do đó số phép so sánh sẽ là N. Vì vậy, độ phức tạp thời gian sẽ là 5Tìm kiếm nhị phânLoại thuật toán tìm kiếm này được sử dụng để tìm vị trí của một giá trị cụ thể có trong một mảng được sắp xếp. Thuật toán tìm kiếm nhị phân hoạt động theo nguyên tắc chia để trị và nó được coi là thuật toán tìm kiếm tốt nhất vì chạy nhanh hơn Bây giờ, hãy lấy một mảng đã sắp xếp làm ví dụ và cố gắng hiểu cách thức hoạt động của nó
Giả sử phần tử mục tiêu được tìm kiếm là 7Phương pháp tìm kiếm nhị phân
Triển khai mãTìm kiếm nhị phân trong Java
Tìm kiếm nhị phân trong Python 0Phân tích độ phức tạp thời gianTrường hợp tốt nhất xảy ra khi phần tử đích là phần tử ở giữa của mảng. Số lần so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp thời gian là 4Trường hợp trung bình. Trung bình, phần tử đích sẽ ở đâu đó trong mảng. Vì vậy, độ phức tạp thời gian sẽ là 9Trường hợp xấu nhất xảy ra khi phần tử đích không có trong danh sách hoặc nó cách xa phần tử ở giữa. Vì vậy, độ phức tạp thời gian sẽ là 9Cách tính độ phức tạp của thời gianGiả sử phép lặp trong Tìm kiếm nhị phân kết thúc sau k lần lặp Tại mỗi lần lặp, mảng được chia cho một nửa. Vì vậy, giả sử độ dài của mảng tại bất kỳ lần lặp nào là N Ở lần lặp 1, 4Ở lần lặp 2, 5Ở lần lặp 3, 6Tại lần lặp k, 7Ngoài ra, chúng ta biết rằng sau k lần chia, độ dài của mảng trở thành 1. Độ dài của mảng = N⁄2k = 1=> N = 2k Nếu chúng ta áp dụng chức năng nhật ký trên cả hai mặt. log2 (N) = log2 (2k)=> log2 (N) = k log2 (2) As (loga (a) = 1) Vì vậy, bây giờ chúng ta có thể thấy tại sao độ phức tạp về thời gian của Tìm kiếm nhị phân là log2 (N) Bạn cũng có thể hình dung hai thuật toán trên bằng công cụ đơn giản do Dipesh Patil xây dựng - Algorithms Visualizer Tìm kiếm nhị phân theo thứ tựGiả sử, chúng ta phải tìm một phần tử đích trong một mảng được sắp xếp. Chúng tôi biết rằng mảng được sắp xếp, nhưng chúng tôi không biết liệu nó được sắp xếp theo thứ tự tăng dần hay giảm dần Phương pháp tìm kiếm nhị phân theo thứ tựCách thực hiện tương tự như tìm kiếm nhị phân ngoại trừ việc chúng ta cần xác định xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Điều này sau đó cho phép chúng tôi đưa ra quyết định về việc tiếp tục tìm kiếm ở nửa bên trái của mảng hay nửa bên phải của mảng
Điều duy nhất chúng ta cần làm là tìm hiểu xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Chúng ta có thể dễ dàng tìm thấy điều này bằng cách so sánh các phần tử đầu tiên và cuối cùng của mảng 0Triển khai mãTìm kiếm nhị phân theo thứ tự trong Java 1Tìm kiếm nhị phân theo thứ tự trong Python 2Phân tích độ phức tạp thời gianSẽ không có thay đổi về độ phức tạp của thời gian, vì vậy nó sẽ giống như Tìm kiếm nhị phân Sự kết luậnTrong bài viết này, chúng ta đã thảo luận về hai trong số các thuật toán tìm kiếm quan trọng nhất cùng với cách triển khai mã của chúng trong Python và Java. Chúng tôi cũng đã xem xét phân tích độ phức tạp thời gian của họ Cảm ơn vì đã đọc Đăng ký nhận bản tin của tôiQUẢNG CÁO QUẢNG CÁO QUẢNG CÁO QUẢNG CÁO QUẢNG CÁO QUẢNG CÁO QUẢNG CÁO QUẢNG CÁO Nhà phát triển ứng dụng tại Thoughtworks Ấn Độ Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn Học cách viết mã miễn phí. Chương trình giảng dạy nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có việc làm với tư cách là nhà phát triển. Bắt đầu Độ phức tạp của tìm kiếm tuyến tính là gì?Do đó, độ phức tạp của tìm kiếm tuyến tính là O(n) . Nếu phần tử được tìm kiếm tồn tại trên khối bộ nhớ đầu tiên thì độ phức tạp sẽ là. Ô(1). Mã cho chức năng tìm kiếm tuyến tính trong JavaScript được hiển thị bên dưới. Hàm này trả về vị trí của mục chúng ta đang tìm kiếm trong mảng.
Độ phức tạp thời gian của thuật toán tuyến tính là gì?Độ phức tạp về thời gian của Tìm kiếm tuyến tính trong trường hợp tốt nhất là O(1) . Trong trường hợp xấu nhất, độ phức tạp thời gian là O(n).
Độ phức tạp thời gian của tìm kiếm tuyến tính và tìm kiếm nhị phân là gì?Biểu đồ so sánh Thuật toán tìm kiếm nhanh nhất trong Python là gì?Nếu bạn biết rằng phần tử bạn đang tìm kiếm có khả năng nằm gần đầu mảng hơn, bạn có thể sử dụng tìm kiếm theo cấp số nhân. Nếu mảng đã sắp xếp của bạn cũng được phân phối đồng đều, thì thuật toán tìm kiếm nhanh nhất và hiệu quả nhất để sử dụng sẽ là tìm kiếm nội suy . |