O (n)에서 길이 n의 정렬되지 않은 배열에서 k 번째로 큰 요소를 찾는 방법은 무엇입니까?
O (n)에서 길이 n의 정렬되지 않은 배열에서 k 번째로 큰 요소를 찾는 방법이 있다고 생각합니다. 또는 아마도 "예상 된"O (n) 또는 무언가 일 것입니다. 우리는 어떻게 이것을 할 수 있습니까?
이것을 k 차 통계량 찾기라고 합니다 . 평균 시간, 최악의 경우 시간을 사용 하는 매우 간단한 무작위 알고리즘 ( quickselect ) O(n)과 O(n^2)최악의 경우를 취하는 매우 복잡한 비 랜덤 화 알고리즘 ( introselect )이 O(n)있습니다. Wikipedia에 대한 정보가 있지만 그다지 좋지 않습니다.
필요한 것은
이 파워 포인트 슬라이드에 있습니다
. O(n)최악의 알고리즘 (introselect) 의 기본 알고리즘을 추출하기 만하면됩니다 .
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
또한 Cormen et al.의 Introduction to Algorithms 책에 자세하게 설명되어 있습니다.
진정한 O(n)알고리즘 을 원한다면 O(kn)이와는 반대로 quickselect를 사용해야합니다 (기본적으로 관심없는 파티션을 버리는 곳은 quicksort입니다). 내 교수진은 런타임 분석을 통해 훌륭한 글을 작성했습니다 : ( reference )
QuickSelect 알고리즘은 정렬되지 않은 n요소 배열에서 k 번째로 작은 요소를 빠르게 찾습니다 . 그것은이다 RandomizedAlgorithm 그래서 우리는 최악의 경우는 계산, 예상 시간을 실행할 수 있습니다.
알고리즘은 다음과 같습니다.
QuickSelect(A, k)
let r be chosen uniformly at random in the range 1 to length(A)
let pivot = A[r]
let A1, A2 be new arrays
# split into a pile A1 of small elements and A2 of big elements
for i = 1 to n
if A[i] < pivot then
append A[i] to A1
else if A[i] > pivot then
append A[i] to A2
else
# do nothing
end for
if k <= length(A1):
# it's in the pile of small elements
return QuickSelect(A1, k)
else if k > length(A) - length(A2)
# it's in the pile of big elements
return QuickSelect(A2, k - (length(A) - length(A2))
else
# it's equal to the pivot
return pivot
이 알고리즘의 실행 시간은 무엇입니까? 적이 우리를 위해 동전을 뒤집 으면 피벗이 항상 가장 큰 요소이고 k항상 1이며
T(n) = Theta(n) + T(n-1) = Theta(n2)그러나 선택 사항이 실제로 임의 인 경우 예상 실행 시간은 다음과 같습니다.
T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))여기서 우리는 재귀가 항상 A1또는 보다 큰 영역에 도달한다고 전적으로 합리적이지 않은 가정을하고있다 A2.
T(n) <= an일부 에 대해 추측 해 봅시다 a. 그럼 우리는 얻는다
T(n)
<= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
= cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n ai이제 어떻게 든 우리는 왼쪽에있는 +를 흡수하기 위해 더하기 부호의 오른쪽에 끔찍한 합계를 가져와야합니다 cn. 우리가 방금 묶었다면 대략적으로 얻을 수 있습니다 . 그러나 이것은 너무 큽니다-여분을 짜낼 공간이 없습니다 . 산술 시리즈 공식을 사용하여 합계를 확장 해 봅시다.2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn
∑i=floor(n/2) to n i
= ∑i=1 to n i - ∑i=1 to floor(n/2) i
= n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
<= n2/2 - (n/4)2/2
= (15/32)n2여기서 우리는 n이 "충분히 크다"는 점을 이용하여 못생긴 floor(n/2)요소를 훨씬 더 깨끗하고 작은 것으로 대체합니다 n/4. 이제 우리는 계속할 수 있습니다
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an제공 a > 16c.
이 제공합니다 T(n) = O(n). 그것은 분명하다 Omega(n). 그래서 우리는 얻는다 T(n) = Theta(n).
그 ( 'kth 가장 큰 요소 배열')에 대한 빠른 Google은 이것을 반환했습니다 : http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
"Make one pass through tracking the three largest values so far."
(특히 3d 최대)
그리고이 답변 :
Build a heap/priority queue. O(n)
Pop top element. O(log n)
Pop top element. O(log n)
Pop top element. O(log n)
Total = O(n) + 3 O(log n) = O(n)
당신은 퀵 정렬을 좋아합니다. 무작위로 원소를 고르고 모든 것을 높이거나 낮추십시오. 이 시점에서 실제로 선택한 요소를 알 수 있으며 수행 한 k 번째 요소 인 경우 bin (높거나 낮은)으로 반복하여 k 번째 요소가 빠지게됩니다. 통계적으로 말하면, 시간 k 번째 원소가 n, O (n)으로 커지는 것을 찾는 데 필요합니다.
프로그래머의 알고리즘 분석 도우미 (Companion to Algorithm Analysis ) 는 O (n) 버전을 제공 하지만 저자는 상수 인자가 너무 높지만 순진한 정렬 목록과 선택 방법을 선호 할 것입니다.
나는 당신의 질문의 편지에 대답했습니다 :)
C ++ 표준 라이브러리는 데이터를 수정하더라도 거의 정확하게 함수 호출을 갖 nth_element습니다. 선형 런타임 O (N)을 예상했으며 부분 정렬도 수행합니다.
const int N = ...;
double a[N];
// ...
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a
O (n) 복잡성에 대해서는 잘 모르지만 O (n)과 nLog (n) 사이에 있어야합니다. 또한 nLog (n)보다 O (n)에 더 가깝습니다. 함수는 자바로 작성
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
나는 동적 프로그래밍, 특히 토너먼트 방법을 사용하여 n 개의 정렬되지 않은 요소에서 k 번째 최소값을 찾는 것을 구현했습니다. 실행 시간은 O (n + klog (n))입니다. 사용 된 메커니즘은 Wikipedia 페이지에서 선택 알고리즘에 대한 방법 중 하나로 나열됩니다 (위의 게시물 중 하나에 표시됨). 내 블로그 페이지 Finding Kth Minimum 에서 알고리즘에 대해 읽고 코드 (java)를 찾을 수 있습니다 . 또한 논리는 목록의 부분 순서를 지정할 수 있습니다-O (klog (n)) 시간으로 첫 K 분 (또는 최대)을 반환합니다.
이 코드는 결과 kth 최소값을 제공했지만 토너먼트 트리를 만들기 위해 수행 된 사전 작업을 무시하고 O (klog (n))에서 k 번째 최대 값을 찾기 위해 유사한 논리를 사용할 수 있습니다.
본 k 가장 큰 요소를 추적하여 시간에 대해서는 O (n + kn) = O (n) (일정한 k의 경우), 공간의 경우 O (k)에서 수행 할 수 있습니다.
배열의 각 요소에 대해 k 가장 큰 목록을 스캔하고 더 큰 경우 가장 작은 요소를 새 요소로 바꿀 수 있습니다.
워렌의 우선 순위 힙 솔루션은 더 깔끔합니다.
Python의 섹시한 빠른 선택
def quickselect(arr, k):
'''
k = 1 returns first element in ascending order.
can be easily modified to return first element in descending order
'''
r = random.randrange(0, len(arr))
a1 = [i for i in arr if i < arr[r]] '''partition'''
a2 = [i for i in arr if i > arr[r]]
if k <= len(a1):
return quickselect(a1, k)
elif k > len(arr)-len(a2):
return quickselect(a2, k - (len(arr) - len(a2)))
else:
return arr[r]
선형 시간에서 배열의 중앙값을 찾은 다음 quicksort에서와 같이 정확하게 파티션 절차를 사용하여 두 부분으로 배열을 나눕니다. 중간 값보다 중간 값보다 작은 값 (<)의 왼쪽과 중간 값보다 큰 값 (>)보다 큰 값 , 또한 lineat 시간에 수행 할 수 있습니다. 이제 k 번째 요소가있는 배열의 해당 부분으로 이동하십시오. 이제 반복은 다음과 같이됩니다.
다음은 정렬되지 않은 알고리즘에서 Kth 요소를 찾기위한 알고리즘이 작동하는 방법에 대한 광범위한 설명과 함께 전체 구현에 대한 링크입니다. 기본 아이디어는 QuickSort에서와 같이 배열을 분할하는 것입니다. 그러나 극단적 인 경우를 피하기 위해 (예 : 모든 단계에서 가장 작은 요소가 피벗으로 선택되어 알고리즘이 O (n ^ 2) 실행 시간으로 변질되는 경우) 중간 값 알고리즘이라는 특수 피벗 선택이 적용됩니다. 전체 솔루션은 최악의 경우 평균 O (n) 시간으로 실행됩니다.
여기에 전체 기사 링크입니다 (이 K 번째 발견에 관한 작은 요소는 있지만 원리는 K 번째 찾는 동일 가장 큰 ) :
이 백서에 따르면 n 개의 항목 목록에서 K 번째로 큰 항목 찾기 다음 알고리즘은 O(n)최악의 경우 시간 이 걸립니다 .
- 배열을 각각 5 개 요소의 n / 5 목록으로 나눕니다.
- 5 개 요소로 구성된 각 하위 배열에서 중앙값을 찾습니다.
- 모든 중앙값의 중앙값을 재귀 적으로 찾아서 M이라고합니다
- 배열을 두 개의 하위 배열로 분할하십시오. 첫 번째 하위 배열에는 M보다 큰 요소가 포함되어 있습니다.이 하위 배열은 a1이고 다른 하위 배열에는 M보다 작은 요소가 포함되어 있습니다.이 하위 배열을 a2라고합니다.
- k <= | a1 |이면 선택 (a1, k)을 반환합니다.
- k− 1 = | a1 |이면 M을 반환합니다.
- k> | a1 | 인 경우 + 1, 반환 선택 (a2, k -a1-1).
분석 : 원본 논문에서 제안한대로 :
중간 값을 사용하여 목록을 두 개의 반쪽으로 분할합니다 (첫 번째 절반은 if
k <= n/2, 두 번째 절반은 그렇지 않습니다). 이러한 알고리즘은 시간이 걸린다cn일부 상수 재귀의 제 1 레벨c,cn/2(우리는 크기 N / 2의리스트에서 재귀 때문에), 다음 단계에서cn/4세번째 레벨 등. 소요 된 총 시간은cn + cn/2 + cn/4 + .... = 2cn = o(n)입니다.
왜 파티션 크기가 3이 아닌 5가됩니까?
원래 논문 에서 언급했듯이 :
목록을 5로 나누면 최악의 경우 70-30으로 나뉩니다. 중간 값보다 중간 값의 절반 이상이 크므로 n / 5 블록의 절반 이상에 3 개의 요소가 있으며 이로 인해
3n/10분할됩니다. 최악의 경우 다른 파티션이 7n / 10임을 의미합니다. 제공 즉T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1, 시간을 실행하는 최악의 경우이다O(n).
이제 위의 알고리즘을 다음과 같이 구현하려고했습니다.
public static int findKthLargestUsingMedian(Integer[] array, int k) {
// Step 1: Divide the list into n/5 lists of 5 element each.
int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
// Step 2: Find pivotal element aka median of medians.
int medianOfMedian = findMedianOfMedians(array, noOfRequiredLists);
//Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
for (Integer element : array) {
if (element < medianOfMedian) {
listWithSmallerNumbers.add(element);
} else if (element > medianOfMedian) {
listWithGreaterNumbers.add(element);
}
}
// Next step.
if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
return -1;
}
public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
int[] medians = new int[noOfRequiredLists];
for (int count = 0; count < noOfRequiredLists; count++) {
int startOfPartialArray = 5 * count;
int endOfPartialArray = startOfPartialArray + 5;
Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
// Step 2: Find median of each of these sublists.
int medianIndex = partialArray.length/2;
medians[count] = partialArray[medianIndex];
}
// Step 3: Find median of the medians.
return medians[medians.length / 2];
}
완료를 위해 다른 알고리즘이 Priority Queue를 사용하고 시간이 걸립니다 O(nlogn).
public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
int p = 0;
int numElements = nums.length;
// create priority queue where all the elements of nums will be stored
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// place all the elements of the array to this priority queue
for (int n : nums) {
pq.add(n);
}
// extract the kth largest element
while (numElements - k + 1 > 0) {
p = pq.poll();
k++;
}
return p;
}
이 두 알고리즘은 다음과 같이 테스트 할 수 있습니다.
public static void main(String[] args) throws IOException {
Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
System.out.println(findKthLargestUsingMedian(numbers, 8));
System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
}
예상되는 출력은 다음과 같습니다. 18 18
이 좀 어떻습니까?
a buffer of length k와 a를 유지하면서 tmp_maxtmp_max를 얻는 것은 O (k)이며 n 번 수행됩니다.O(kn)
맞습니까? 아니면 뭔가 빠졌습니까?
비록 퀵 셀렉트와 최악의 중간 통계 방법의 경우를 능가하지는 않지만 이해하고 구현하기가 쉽습니다.
목록을 반복합니다. 현재 값이 저장된 가장 큰 값보다 큰 경우 가장 큰 값으로 저장하고 1-4를 낮추고 5를 떨어 뜨립니다. 그렇지 않은 경우 2 번과 비교하고 동일한 작업을 수행하십시오. 5 개의 저장된 값을 모두 확인하면서 반복하십시오. 이것은 O (n)에서해야합니다.
하나의 답변을 제안하고 싶습니다
첫 번째 k 요소를 가져 와서 k 값의 연결된 목록으로 정렬하면
최악의 경우에도 나머지 nk 값에 대한 삽입 정렬을 수행하면 최악의 경우에도 다른 모든 값의 경우 k * (nk)가되고 이전 k 값을 정렬하려면 k * (k- 1) 따라서 (nk-k)는 o (n)입니다.
건배
n에서 k 번째로 큰 정수를 찾는 중간 알고리즘 중위 알고리즘에 대한 설명은 여기에서 찾을 수 있습니다. http://cs.indstate.edu/~spitla/presentation.pdf
C ++ 구현은 다음과 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMedian(vector<int> vec){
// Find median of a vector
int median;
size_t size = vec.size();
median = vec[(size/2)];
return median;
}
int findMedianOfMedians(vector<vector<int> > values){
vector<int> medians;
for (int i = 0; i < values.size(); i++) {
int m = findMedian(values[i]);
medians.push_back(m);
}
return findMedian(medians);
}
void selectionByMedianOfMedians(const vector<int> values, int k){
// Divide the list into n/5 lists of 5 elements each
vector<vector<int> > vec2D;
int count = 0;
while (count != values.size()) {
int countRow = 0;
vector<int> row;
while ((countRow < 5) && (count < values.size())) {
row.push_back(values[count]);
count++;
countRow++;
}
vec2D.push_back(row);
}
cout<<endl<<endl<<"Printing 2D vector : "<<endl;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
cout<<vec2D[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
// Calculating a new pivot for making splits
int m = findMedianOfMedians(vec2D);
cout<<"Median of medians is : "<<m<<endl;
// Partition the list into unique elements larger than 'm' (call this sublist L1) and
// those smaller them 'm' (call this sublist L2)
vector<int> L1, L2;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
if (vec2D[i][j] > m) {
L1.push_back(vec2D[i][j]);
}else if (vec2D[i][j] < m){
L2.push_back(vec2D[i][j]);
}
}
}
// Checking the splits as per the new pivot 'm'
cout<<endl<<"Printing L1 : "<<endl;
for (int i = 0; i < L1.size(); i++) {
cout<<L1[i]<<" ";
}
cout<<endl<<endl<<"Printing L2 : "<<endl;
for (int i = 0; i < L2.size(); i++) {
cout<<L2[i]<<" ";
}
// Recursive calls
if ((k - 1) == L1.size()) {
cout<<endl<<endl<<"Answer :"<<m;
}else if (k <= L1.size()) {
return selectionByMedianOfMedians(L1, k);
}else if (k > (L1.size() + 1)){
return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
}
}
int main()
{
int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
vector<int> vec(values, values + 25);
cout<<"The given array is : "<<endl;
for (int i = 0; i < vec.size(); i++) {
cout<<vec[i]<<" ";
}
selectionByMedianOfMedians(vec, 8);
return 0;
}
Wirth의 선택 알고리즘 도 있는데 , 이는 QuickSelect보다 간단한 구현입니다. Wirth의 선택 알고리즘은 QuickSelect보다 느리지 만 약간의 개선으로 더 빠릅니다.
더 자세하게. Vladimir Zabrodsky의 MODIFIND 최적화와 중위값 피벗 선택을 사용하고 알고리즘의 파티셔닝 부분의 마지막 단계에주의를 기울이면서 다음 알고리즘 (상상적으로 "LefSelect"라고 함)을 만들었습니다.
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
int l=0, m = n-1, i=l, j=m;
float x;
while (l<m) {
if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
if( a[j] < a[k] ) F_SWAP(a[k],a[j]);
x=a[k];
while (j>k & i<k) {
do i++; while (a[i]<x);
do j--; while (a[j]>x);
F_SWAP(a[i],a[j]);
}
i++; j--;
if (j<k) {
while (a[i]<x) i++;
l=i; j=m;
}
if (k<i) {
while (x<a[j]) j--;
m=j; i=l;
}
}
return a[k];
}
내가 한 벤치 마크에서 여기 , LefSelect은 20 ~ 30 % 더 빠른 QuickSelect보다.
하스켈 솔루션 :
kthElem index list = sort list !! index
withShape ~[] [] = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys
sort [] = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
where
ls = filter (< x)
rs = filter (>= x)
이는 withShape 메소드를 사용하여 실제로 계산하지 않고 파티션의 크기를 발견함으로써 중간 솔루션의 중앙값을 구현합니다.
다음은 Randomized QuickSelect의 C ++ 구현입니다. 아이디어는 피벗 요소를 임의로 선택하는 것입니다. 무작위 파티션을 구현하기 위해 랜덤 함수 rand ()를 사용하여 l과 r 사이의 인덱스를 생성하고 무작위로 생성 된 인덱스의 요소를 마지막 요소와 바꾸고 마지막 요소를 피벗으로 사용하는 표준 파티션 프로세스를 호출합니다.
#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;
int randomPartition(int arr[], int l, int r);
// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]); // swap the pivot
return i;
}
// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return partition(arr, l, r);
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;
cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}
위의 솔루션의 최악의 시간 복잡도는 여전히 O (n2)입니다. 최악의 경우 무작위 함수는 항상 모서리 요소를 선택할 수 있습니다. 임의 추출 QuickSelect의 예상 시간 복잡도는 Θ (n)입니다.
- 우선 순위 큐를 작성하십시오.
- 모든 요소를 힙에 삽입하십시오.
poll ()을 k 번 호출하십시오.
public static int getKthLargestElements(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>((x , y) -> (y-x)); //insert all the elements into heap for(int ele : arr) pq.offer(ele); // call poll() k times int i=0; while(i<k) { int result = pq.poll(); } return result; }
이것은 자바 스크립트로 구현 된 것입니다.
당신이 배열을 수정할 수 없다는 제약을 해제하는 경우, 당신은 고전 퀵 스타일 ( "현재 파티션"을 식별하기 위해 두 개의 인덱스를 사용하여 추가 메모리의 사용을 방지 할 수 있습니다 - http://www.nczonline.net/blog/2012/ 11 / 27 / computer-science-in-javascript-quicksort / ).
function kthMax(a, k){
var size = a.length;
var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2)
//Create an array with all element lower than the pivot and an array with all element higher than the pivot
var i, lowerArray = [], upperArray = [];
for (i = 0; i < size; i++){
var current = a[i];
if (current < pivot) {
lowerArray.push(current);
} else if (current > pivot) {
upperArray.push(current);
}
}
//Which one should I continue with?
if(k <= upperArray.length) {
//Upper
return kthMax(upperArray, k);
} else {
var newK = k - (size - lowerArray.length);
if (newK > 0) {
///Lower
return kthMax(lowerArray, newK);
} else {
//None ... it's the current pivot!
return pivot;
}
}
}
수행 방법을 테스트하려는 경우 다음 변형을 사용할 수 있습니다.
function kthMax (a, k, logging) {
var comparisonCount = 0; //Number of comparison that the algorithm uses
var memoryCount = 0; //Number of integers in memory that the algorithm uses
var _log = logging;
if(k < 0 || k >= a.length) {
if (_log) console.log ("k is out of range");
return false;
}
function _kthmax(a, k){
var size = a.length;
var pivot = a[parseInt(Math.random()*size)];
if(_log) console.log("Inputs:", a, "size="+size, "k="+k, "pivot="+pivot);
// This should never happen. Just a nice check in this exercise
// if you are playing with the code to avoid never ending recursion
if(typeof pivot === "undefined") {
if (_log) console.log ("Ops...");
return false;
}
var i, lowerArray = [], upperArray = [];
for (i = 0; i < size; i++){
var current = a[i];
if (current < pivot) {
comparisonCount += 1;
memoryCount++;
lowerArray.push(current);
} else if (current > pivot) {
comparisonCount += 2;
memoryCount++;
upperArray.push(current);
}
}
if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);
if(k <= upperArray.length) {
comparisonCount += 1;
return _kthmax(upperArray, k);
} else if (k > size - lowerArray.length) {
comparisonCount += 2;
return _kthmax(lowerArray, k - (size - lowerArray.length));
} else {
comparisonCount += 2;
return pivot;
}
/*
* BTW, this is the logic for kthMin if we want to implement that... ;-)
*
if(k <= lowerArray.length) {
return kthMin(lowerArray, k);
} else if (k > size - upperArray.length) {
return kthMin(upperArray, k - (size - upperArray.length));
} else
return pivot;
*/
}
var result = _kthmax(a, k);
return {result: result, iterations: comparisonCount, memory: memoryCount};
}
나머지 코드는 놀이터를 만드는 것입니다.
function getRandomArray (n){
var ar = [];
for (var i = 0, l = n; i < l; i++) {
ar.push(Math.round(Math.random() * l))
}
return ar;
}
//Create a random array of 50 numbers
var ar = getRandomArray (50);
이제 몇 번 테스트를 실행하십시오. Math.random () 때문에 매번 다른 결과가 생성됩니다.
kthMax(ar, 2, true);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 34, true);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
몇 번 테스트하면 반복 횟수가 평균 O (n) ~ = constant * n이고 k 값이 알고리즘에 영향을 미치지 않는다는 것을 경험적으로 볼 수 있습니다.
이 알고리즘을 생각해 냈고 O (n) 인 것 같습니다.
k = 3이라고 가정하고 배열에서 세 번째로 큰 항목을 찾고 싶습니다. 세 개의 변수를 만들고 배열의 각 항목을이 세 변수 중 최소값과 비교합니다. 배열 항목이 최소값보다 크면 min 변수를 항목 값으로 바꿉니다. 우리는 배열이 끝날 때까지 같은 것을 계속합니다. 세 변수 중 최소값은 배열에서 세 번째로 큰 항목입니다.
define variables a=0, b=0, c=0
iterate through the array items
find minimum a,b,c
if item > min then replace the min variable with item value
continue until end of array
the minimum of a,b,c is our answer
그리고 K 번째로 큰 항목을 찾으려면 K 변수가 필요합니다.
예 : (k = 3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
누군가 이것을 검토하고 내가 누락 된 것을 알려주십시오.
다음은 eladv가 제안한 알고리즘의 구현입니다.
public class Median {
public static void main(String[] s) {
int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
System.out.println(selectK(test,8));
/*
int n = 100000000;
int[] test = new int[n];
for(int i=0; i<test.length; i++)
test[i] = (int)(Math.random()*test.length);
long start = System.currentTimeMillis();
random_selectK(test, test.length/2);
long end = System.currentTimeMillis();
System.out.println(end - start);
*/
}
public static int random_selectK(int[] a, int k) {
if(a.length <= 1)
return a[0];
int r = (int)(Math.random() * a.length);
int p = a[r];
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return random_selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return random_selectK(temp,k-small-equal);
}
}
public static int selectK(int[] a, int k) {
if(a.length <= 5) {
Arrays.sort(a);
return a[k-1];
}
int p = median_of_medians(a);
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return selectK(temp,k-small-equal);
}
}
private static int median_of_medians(int[] a) {
int[] b = new int[a.length/5];
int[] temp = new int[5];
for(int i=0; i<b.length; i++) {
for(int j=0; j<5; j++)
temp[j] = a[5*i + j];
Arrays.sort(temp);
b[i] = temp[2];
}
return selectK(b, b.length/2 + 1);
}
}
이는 임의의 피벗을 선택하고 더 작은 요소를 왼쪽으로 가져오고 더 큰 요소를 오른쪽으로 가져 오는 quickSort 전략과 유사합니다.
public static int kthElInUnsortedList(List<int> list, int k)
{
if (list.Count == 1)
return list[0];
List<int> left = new List<int>();
List<int> right = new List<int>();
int pivotIndex = list.Count / 2;
int pivot = list[pivotIndex]; //arbitrary
for (int i = 0; i < list.Count && i != pivotIndex; i++)
{
int currentEl = list[i];
if (currentEl < pivot)
left.Add(currentEl);
else
right.Add(currentEl);
}
if (k == left.Count + 1)
return pivot;
if (left.Count < k)
return kthElInUnsortedList(right, k - left.Count - 1);
else
return kthElInUnsortedList(left, k);
}
이 링크의 끝으로 이동 : ...........
O (n) 시간과 일정한 공간에서 k 번째로 작은 요소를 찾을 수 있습니다. 우리가 배열을 정수로만 고려한다면.
이 방법은 배열 값 범위에서 이진 검색을 수행하는 것입니다. 정수 범위에 min_value와 max_value가 모두 있으면 해당 범위에서 이진 검색을 수행 할 수 있습니다. 어떤 값이 kth-smallest 또는 kth-smallest보다 크거나 kth-smallest보다 큰지를 알려주는 비교기 함수를 작성할 수 있습니다. k 번째로 작은 숫자에 도달 할 때까지 이진 검색을 수행하십시오.
그 코드는 다음과 같습니다
클래스 솔루션 :
def _iskthsmallest(self, A, val, k):
less_count, equal_count = 0, 0
for i in range(len(A)):
if A[i] == val: equal_count += 1
if A[i] < val: less_count += 1
if less_count >= k: return 1
if less_count + equal_count < k: return -1
return 0
def kthsmallest_binary(self, A, min_val, max_val, k):
if min_val == max_val:
return min_val
mid = (min_val + max_val)/2
iskthsmallest = self._iskthsmallest(A, mid, k)
if iskthsmallest == 0: return mid
if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
return self.kthsmallest_binary(A, mid+1, max_val, k)
# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
if not A: return 0
if k > len(A): return 0
min_val, max_val = min(A), max(A)
return self.kthsmallest_binary(A, min_val, max_val, k)
quickselect 알고리즘보다 우수한 알고리즘도 있습니다. 이를 Floyd-Rivets (FR) 알고리즘이라고 합니다.
원본 기사 : https://doi.org/10.1145/360680.360694
다운로드 가능한 버전 : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf
Wikipedia article https://ko.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
C ++에서 quickselect 및 FR 알고리즘을 구현하려고했습니다. 또한 표준 C ++ 라이브러리 구현 std :: nth_element (기본적으로 quickselect 및 heapselect의 introselect 하이브리드)와 비교했습니다. 결과는 quickselect이고 nth_element는 평균적으로 비슷한 수준으로 실행되었지만 FR 알고리즘은 약 그들에 비해 두 배 빠릅니다.
FR 알고리즘에 사용한 샘플 코드 :
template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
if (n == 0)
return *(std::min_element(data.begin(), data.end()));
else if (n == data.size() - 1)
return *(std::max_element(data.begin(), data.end()));
else
return _FRselect(data, 0, data.size() - 1, n);
}
template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
size_t leftIdx = left;
size_t rightIdx = right;
while (rightIdx > leftIdx)
{
if (rightIdx - leftIdx > 600)
{
size_t range = rightIdx - leftIdx + 1;
long long i = n - (long long)leftIdx + 1;
long long z = log(range);
long long s = 0.5 * exp(2 * z / 3);
long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);
size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);
_FRselect(data, newLeft, newRight, n);
}
T t = data[n];
size_t i = leftIdx;
size_t j = rightIdx;
// arrange pivot and right index
std::swap(data[leftIdx], data[n]);
if (data[rightIdx] > t)
std::swap(data[rightIdx], data[leftIdx]);
while (i < j)
{
std::swap(data[i], data[j]);
++i; --j;
while (data[i] < t) ++i;
while (data[j] > t) --j;
}
if (data[leftIdx] == t)
std::swap(data[leftIdx], data[j]);
else
{
++j;
std::swap(data[j], data[rightIdx]);
}
// adjust left and right towards the boundaries of the subset
// containing the (k - left + 1)th smallest element
if (j <= n)
leftIdx = j + 1;
if (n <= j)
rightIdx = j - 1;
}
return data[leftIdx];
}
template <typename T>
int sgn(T val) {
return (T(0) < val) - (val < T(0));
}
내가 할 일은 이것입니다 :
initialize empty doubly linked list l
for each element e in array
if e larger than head(l)
make e the new head of l
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
링크 된 목록에서 첫 번째 요소와 마지막 요소에 대한 포인터를 간단히 저장할 수 있습니다. 목록을 업데이트 할 때만 변경됩니다.
최신 정보:
initialize empty sorted tree l
for each element e in array
if e between head(l) and tail(l)
insert e into l // O(log k)
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
먼저 우리는 O (n) 시간이 걸리는 분류되지 않은 배열에서 BST를 만들 수 있으며 BST에서 O (n (n))의 가장 작은 요소를 찾을 수 있습니다.
'Programing' 카테고리의 다른 글
| getDefaultSharedPreferences와 getSharedPreferences의 차이점 (0) | 2020.04.26 |
|---|---|
| 로컬 저장소에서 원격 Git 저장소를 작성하는 방법은 무엇입니까? (0) | 2020.04.26 |
| Numpy 배열에서 Pandas DataFrame 만들기 : 인덱스 열과 열 머리글을 어떻게 지정합니까? (0) | 2020.04.26 |
| 지정된 디렉토리에 npm을 설치하는 방법은 무엇입니까? (0) | 2020.04.26 |
| ES6 약속이 있으므로 Q 또는 BlueBird와 같은 약속 라이브러리를 사용해야 할 이유가 있습니까? (0) | 2020.04.26 |