Tôi muốn viết chương trình để tìm phần tử nhỏ nhất thứ n mà không cần sử dụng bất kỳ kỹ thuật phân loại nào.Tìm phần tử nhỏ nhất thứ n trong mảng mà không cần sắp xếp?
Chúng ta có thể thực hiện nó một cách đệ quy, chia và chinh phục kiểu như sắp xếp nhanh không?
Nếu không, làm cách nào?
Bạn có thể tìm thông tin về sự cố đó tại đây: Selection algorithm.
Hai ngăn xếp có thể được sử dụng như thế này để định vị số nhỏ nhất thứ N trong một lần truyền.
tôi thường đồng ý với phân tích tối ưu hóa Noldorins'.
Giải pháp ngăn xếp này hướng tới một sơ đồ đơn giản sẽ hoạt động (với chuyển động dữ liệu tương đối hơn - trên hai ngăn xếp). Lược đồ heap giảm số lần tìm kiếm số nhỏ nhất Nth xuống cây ngang qua (log m).
Nếu mục tiêu của bạn là giải pháp tối ưu (nói cho một tập hợp lớn số hoặc có thể cho một bài tập lập trình, trong đó tối ưu hóa và trình diễn nó rất quan trọng), bạn nên sử dụng kỹ thuật heap.
Giải pháp ngăn xếp có thể được nén trong yêu cầu không gian bằng cách triển khai hai ngăn xếp trong cùng một không gian của phần tử K (trong đó K là kích thước của tập dữ liệu của bạn). Vì vậy, nhược điểm chỉ là chuyển động chồng thêm khi bạn chèn.
Nhiệm vụ này là hoàn toàn có thể hoàn thành trong vòng khoảng O(n) thời gian (n là độ dài của danh sách) bằng cách sử dụng một heap structure (cụ thể là, một priority queue dựa trên một Fibonacci heap), mang đến cho O(1) thời gian chèn và O(log n) thời gian xóa).
Xem xét nhiệm vụ truy xuất phần tử nhỏ nhất thứ m từ danh sách. Chỉ cần lặp qua danh sách và thêm từng mục vào hàng đợi ưu tiên (có kích thước m), bạn có thể tạo hàng đợi của từng mục trong danh sách trong thời gian O(n) (hoặc có thể ít hơn bằng cách sử dụng một số tối ưu hóa, mặc dù tôi không chắc chắn điều này là cực kỳ hữu ích).Sau đó, việc xóa phần tử có mức ưu tiên thấp nhất trong hàng đợi (ưu tiên cao nhất là mục nhỏ nhất), chỉ mất O(log m) tổng thời gian và bạn đã hoàn tất.
Vì vậy, tổng thể, mức độ phức tạp của thuật toán sẽ là O(n + log n), nhưng kể từ khi log n << n (ví dụ: n phát triển nhanh hơn rất nhiều so với log n), điều này làm giảm chỉ đơn giản là O(n). Tôi không nghĩ rằng bạn sẽ có thể nhận được bất cứ điều gì đáng kể hiệu quả hơn so với điều này trong trường hợp chung.
(1) làm thế nào để bạn có được hàng đợi ưu tiên "có kích thước m"? bằng cách nào đó nó biết đó là món đồ lớn nhất để vứt đi khi bạn thêm một thứ khác? (2) giả sử bạn có một cấu trúc như vậy, tôi vẫn không thấy làm thế nào bạn có O (log m). bạn không cần phải nhân với m bởi vì bạn cần phải loại bỏ những thứ m để có được mục nhỏ nhất m'th? – newacct
@newacct: Về cơ bản, bạn đang đúng về điểm 1. Bạn có thể giới hạn kích thước của hàng đợi ưu tiên ở một mức độ nào đó (ví dụ: bằng cách kiểm tra mục tối đa sau khi điền), nhưng không giới hạn kích thước m. Về điểm 2, điều đó không đúng. Thực tế bạn có thể lấy ra mục lớn nhất trong thời gian log n (thay vì m, với việc sửa điểm 1) - hàng đợi ưu tiên cho phép truy cập vào các mục max hoặc min trong thời gian log n; nó chỉ là những người bắt đầu mất nhiều thời gian hơn để tìm nạp. – Noldorin
Tại sao giải pháp của tôi ở trên không tốt nhất? .. Tôi muốn tìm hiểu vấn đề với giải pháp của tôi – Learner
Điều bạn đang đề cập đến là Thuật toán lựa chọn, như đã lưu ý trước đây. Cụ thể, tham chiếu đến quicksort cho thấy bạn đang nghĩ đến số partition based selection.
Dưới đây là cách hoạt động:
Thuật toán này cũng tốt cho việc tìm danh sách các phần tử m cao nhất được sắp xếp ... chỉ cần chọn phần tử lớn nhất m'th và sắp xếp danh sách ở trên phần tử đó. Hoặc, đối với một thuật toán nhanh hơn một chút, hãy thực hiện thuật toán Quicksort, nhưng từ chối để recurse vào các khu vực không chồng chéo khu vực mà bạn muốn tìm các giá trị được sắp xếp.
Điều thực sự gọn gàng về điều này là nó thường chạy trong thời gian O (n). Lần đầu tiên thông qua, nó thấy toàn bộ danh sách. Trên đệ quy đầu tiên, nó thấy khoảng một nửa, sau đó một phần tư, vv Vì vậy, nó nhìn vào khoảng 2n yếu tố, do đó nó chạy trong O (n) thời gian. Thật không may, như trong quicksort, nếu bạn liên tục chọn một trục xấu, bạn sẽ chạy trong thời gian O (n).
Bạn có thể sử dụng phân vùng nhị phân, nếu bạn không muốn sử dụng đống heap.
Algo:
contruct đống nhị phân phút từ mảng hoạt động này sẽ mất O (n) thời gian.
Vì đây là một đống nhị phân nhỏ, phần tử ở gốc là giá trị tối thiểu.
Vì vậy, tiếp tục xóa phần tử gốc frm, cho đến khi bạn nhận được giá trị nhỏ nhất kth thứ k. o (1) hoạt động
Đảm bảo sau mỗi lần xóa, bạn sẽ lưu trữ lại hoạt động heap kO (logn).
Vì vậy, thời gian chạy đây là O (klogn) + O (n) ............ vì thế nó là O (klogn) ...
Here is the Ans to find Kth smallest element from an array:
#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
int Nthmin=0,j=0,i;
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall);
int main()
{
int size;
cout<<"Enter Size of array\n";
cin>>size;
int *arr=(int*)malloc(sizeof(int)*size);
cout<<"\nEnter array elements\n";
for(i=0;i<size;i++)
cin>>*(arr+i);
cout<<"\n";
for(i=0;i<size;i++)
cout<<*(arr+i)<<" ";
cout<<"\n";
int n=sizeof(arr)/sizeof(int);
int result=GetNthSmall(arr,size,3);
printf("Result = %d",result);
getch();
return 0;
}
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall)
{
int min=numbers[0];
while(j<Nthsmall)
{
Nthmin=numbers[0];
for(i=1;i<NoOfElements;i++)
{
if(j==0)
{
if(numbers[i]<min)
{
min=numbers[i];
}
Nthmin=min;
}
else
{
if(numbers[i]<Nthmin && numbers[i]>min)
Nthmin=numbers[i];
}
}
min=Nthmin;
j++;
}
return Nthmin;
}
Âm thanh như thuật toán này nói chung là thời gian O (nm), n là chiều dài danh sách, m như trong phần tử nhỏ nhất thứ m. – Noldorin
Đây chỉ là một loại sắp xếp. – newacct
Có, đây chỉ là phân loại bằng cách sử dụng ngăn xếp – Learner