Tìm phần tử nhỏ nhất trong một mảng có mẫu

Question

Một mảng được đưa ra sao cho giá trị của phần tử tăng từ chỉ số 0 thông qua chỉ mục (k -1). Tại k giá trị tối thiểu và giá trị này bắt đầu tăng trở lại thông qua yếu tố thứ n. Tìm phần tử tối thiểu.

Về cơ bản, danh sách được sắp xếp của nó được thêm vào danh sách khác; ví dụ: (1, 2, 3, 4, , 1, 2, 3).

Tôi đã thử tất cả các loại thuật toán như buliding min-heap, chọn nhanh hoặc chỉ đơn giản đi ngang qua. Nhưng không thể có được nó dưới O (n). Nhưng có một mô hình trong mảng này, một cái gì đó đề nghị loại tìm kiếm nhị phân của điều nên có thể, và phức tạp nên được một cái gì đó như O (log n), nhưng không thể tìm thấy bất cứ điều gì. Suy nghĩ ??

Cảm ơn

Answer 1

Không Sự sụt giảm có thể ở bất kỳ đâu, không có cấu trúc này.

Hãy xem xét những thái cực

1234567890 
9
1234056789 
1357024689 

Nó làm giảm tới việc tìm kiếm các yếu tố tối thiểu.

Answer 2

Thực hiện tìm kiếm nhị phân theo chiều rộng cho phạm vi giảm, với chồng chéo một phần tử tại phần tách nhị phân. Nói cách khác, nếu bạn có, ví dụ: 17 phần tử, so sánh các yếu tố

0,8 
8,16 
0,4 
4,8 
8,12 
12,16 
0,2 
2,4 

v.v., tìm trường hợp phần tử bên trái lớn hơn bên phải.

Khi bạn tìm thấy phạm vi như vậy, hãy recurse, thực hiện tìm kiếm nhị phân tương tự trong phạm vi đó. Lặp lại cho đến khi bạn tìm thấy cặp giảm liền kề.

Độ phức tạp trung bình không nhỏ hơn O (log n), với trường hợp xấu nhất là O (n). Bất cứ ai có thể có được một ước tính phức tạp trung bình chặt chẽ hơn? Nó có vẻ gần "giữa" O (log n) và O (n), nhưng tôi không thấy cách đánh giá nó. Nó cũng phụ thuộc vào bất kỳ ràng buộc bổ sung nào trên phạm vi giá trị và kích thước tăng từ thành viên này sang thành viên khác.

Nếu gia số giữa các phần tử luôn là 1, thì có giải pháp O (log n).

Answer 3

Nó không thể được thực hiện trong ít hơn O (n).

Trường hợp xấu nhất của loại hình này sẽ luôn giữ phiền chúng tôi -

Một danh sách tăng a1, a2, a3 .... ak, ak + 1 ... một

chỉ với một độ lệch ak < ak-1 ví dụ 1,2,3,4,5,6,4,7,8,9,10

Và tất cả các số khác giữ hoàn toàn không thông tin về giá trị của 'k' hoặc 'ak'

Answer 4

Giải pháp đơn giản nhất là chỉ cần nhìn về phía trước thông qua danh sách cho đến khi giá trị tiếp theo nhỏ hơn giá trị hiện tại hoặc ngược lại để tìm giá trị lớn hơn giá trị hiện tại. Đó là O (n).

Làm cả hai đồng thời sẽ vẫn là O (n) nhưng thời gian chạy có thể sẽ nhanh hơn (tùy thuộc vào các yếu tố bộ nhớ/bộ xử lý phức tạp).

Tôi không nghĩ rằng bạn có thể làm cho thuật toán nhanh hơn nhiều so với O (n) vì rất nhiều thuật toán tìm kiếm phân chia và dựa trên việc có tập dữ liệu được sắp xếp.