Độ phức tạp về thời gian tìm kiếm nhị phân đối với mảng không được phân loại

Question

Tôi bị kẹt với hai độ phức tạp thời gian. Để thực hiện tìm kiếm nhị phân với mảng được sắp xếp là O (logN). Vì vậy, để tìm kiếm một mảng chưa phân loại, chúng ta phải sắp xếp nó đầu tiên để trở thành O (NlogN). Vì vậy, sau đó chúng tôi có thể thực hiện tìm kiếm nhị phân cung cấp cho sự phức tạp như O (N) nhưng tôi đã đọc rằng nó có thể là O (NlogN). Đó là chính xác?

Answer 1

Tìm kiếm nhị phân dành cho danh sách "Đã sắp xếp". Độ phức tạp là O (logn).

Tìm kiếm nhị phân không hoạt động đối với danh sách "chưa phân loại". Đối với những danh sách này chỉ cần thực hiện tìm kiếm thẳng bắt đầu từ phần tử đầu tiên; điều này mang lại sự phức tạp của O (n). Nếu bạn sắp xếp mảng với MergeSort hoặc bất kỳ thuật toán O (nlogn) nào khác thì độ phức tạp sẽ là O (nlogn).

O (logn) < O (n) < O (nlogn)

Answer 2

Câu trả lời cho câu hỏi của bạn là trong câu hỏi của bạn riêng của mình. Trước tiên, bạn sắp xếp danh sách. Nếu bạn sắp xếp danh sách của mình bằng cách sử dụng sắp xếp nhanh hoặc hợp nhất, độ phức tạp sẽ trở thành o (n nhật ký n). Phần 1 đã kết thúc. Phần thứ hai của việc thực hiện tìm kiếm nhị phân được thực hiện trên 'Danh sách được sắp xếp'. Độ phức tạp của tìm kiếm nhị phân là o (log n). Do đó cuối cùng sự phức tạp của chương trình vẫn là o (n log n). Tuy nhiên, nếu bạn muốn tính trung bình của mảng, bạn không phải sắp xếp danh sách. Một ứng dụng đơn giản của một tuyến tính, hoặc tuần tự, tìm kiếm có thể giúp bạn với điều đó.

Answer 3

Độ phức tạp của tìm kiếm tuyến tính là O(n) và tìm kiếm nhị phân là O(log n) (log-2). Nếu chúng ta có một mảng chưa được phân loại và muốn sử dụng tìm kiếm nhị phân cho điều này, chúng ta phải sắp xếp mảng đầu tiên. Và ở đây chúng ta phải dành thời gian O(n logn) để sắp xếp mảng và sau đó dành thời gian để tìm kiếm phần tử.