알고리즘 학습 (1): 최소 k 개 수 를 찾 습 니 다.

제목.
제목 설명: 가장 작은 k 개 요 소 를 찾 습 니 다. 제목: n 개의 정 수 를 입력 하고 그 중에서 가장 작은 k 개 를 출력 합 니 다. 예 를 들 어 1, 2, 3, 4, 5, 6, 7, 8 을 입력 하면 가장 작은 4 개 수 는 1, 2, 3, 4 입 니 다.
사고의 방향
첫째, 가장 쉽게 생각 할 수 있 는 것 은 정렬 이다. 그 다음 에 앞의 k 개 요 소 를 출력 하고 빠 른 정렬 을 한다. 정렬 시간 은 n * logn 이다. 게다가 출력 전의 k 개 요 소 를 옮 겨 다 니 면 전체적인 시간 복잡 도 는 n * logn + k = O (n * logn) 2 이다. 사실은 문제 에서 출력 전의 k 개 수 만 요구 하고 이 수 는 순서 가 있 으 며 n 개 수 를 정렬 할 필요 가 없다.n 개 수 에서 먼저 앞의 k 개 수 를 꺼 내 서 한 배열 에 넣 은 다음 에 이 k 개 수 를 선택 하여 정렬 하거나 정렬 을 교환 합 니 다. kmax 라 는 k 개 수의 가장 큰 수 를 찾 아 사용 할 때 O (k) 를 찾 습 니 다.그 다음 에 남 은 n - k 개 수 에서 순서대로 x 를 꺼 내 kmax 와 비교 하면 if x > kmax 를 건 너 뛰 고 if x < kmax, kmax = x 를 건 너 뛴 다음 에 이 k 개 수 를 선택 하여 정렬 하여 가장 큰 kmax 를 찾 습 니 다. 전체적인 시간 복잡 도 는 평균 적 으로 n * O (k) 입 니 다. 이용 하 는 것 은 가장 작은 앞의 k 개 수 를 찾 는 것 입 니 다. 가장 큰 것 보다 크 면 안에 없 을 것 입 니 다. 가장 큰 것 보다 작 으 면...이 가능 하 다, ~ 할 수 있다,...3. 우 리 는 사고 2 중의 k 개 수의 조작 을 개선 할 수 있 습 니 다. 바로 k 개 수의 kmax 를 찾 는 것 입 니 다. 최대 더 미 를 사용 하여 k 개 요소 의 최대 더 미 를 유지 할 수 있 습 니 다. 쌓 는 데 걸 리 는 시간 O (k) 입 니 다. 이때 쌓 인 뿌리 노드 는 가장 큰 kmax 입 니 다. 그리고 남 은 n - k 개 요 소 를 옮 겨 다 니 며 if x > kmax 를 건 너 뛰 고 if x < kmax, kmax = x, 최대 더 미 를 업데이트 하고 시간 복잡 도 는 O (logk) 입 니 다.총 시간 복잡 도 는 O (n * logk) 입 니 다.넷 째, 우리 의 목적 은 가장 작은 k 개 수 를 찾 는 것 이다. 만약 에 이 k 개 수 를 왼쪽 에 놓 으 면 오른쪽 에 있 는 것 이 모두 그들 보다 크 고 직접 출력 하면 된다. 이것 은 바로 빠 른 정렬 의 사고 이다.n 개의 수 는 배열 S 에 존재 합 니 다. 무 작위 로 하나의 수 X 를 중심 요소 로 선택 하고 배열 을 Sa 와 Sb 두 부분 으로 나 누 었 습 니 다. Sa < = X < = Sb. 찾 으 려 는 개수 k 가 size of (Sa) 보다 작 으 면 Sa 의 앞 k 개 요 소 를 되 돌려 줍 니 다. 그렇지 않 으 면 Sa 의 모든 요소 + SB 의 작은 k - size of (Sa) 요 소 를 되 돌려 줍 니 다.이 알고리즘 의 관건 은 바로 이 중추 요소 의 선택 이다. 무 작위 로 중추 요 소 를 선택 하면 선형 기대 시간 O (n) 를 할 수 있다.우리 가 흔히 알 고 있 는 빠 른 순 서 는 고정된 첫 번 째 또는 마지막 을 중심 으로 하 는 것 이다. 매번 재 귀 구분 이 고 르 지 않다. 마지막 평균 시간 복잡 도 는 O (n * logn) 이 고 RANDOMIZED - SELECT (데이터 구조 와 알고리즘 분석 - c 언어 설명 P185) 가 제시 한 선택 에 대한 선형 기대 시간 은 일반적인 빠 른 배열 과 달리 매번 무 작위 이다.무 작위 적 인 방법 은 '중위 수의 중위 수', '중 항의 중 항 을 5 분화 하 는 것' 이 있다.다섯 째, 선형 시간 정렬, 계수 정렬 을 사용 할 수 있 습 니 다. 시간 복잡 도 는 O (n) 6 에 달 합 니 다. 가장 작은 앞의 k 개 수 를 찾 는 이상 우 리 는 최소 더 미 를 사용 할 수 있 습 니 다. n 개 요소 가 있 는 배열 을 최소 더 미 를 만 들 수 있 습 니 다. 사용 할 때 O (n) 는 더미 에서 k 횟수 를 취하 고 한 번 을 취하 면 최소 더 미 를 다시 배열 하여 최소 더 미 를 확보 해 야 합 니 다. 매번 평균 적 으로 사용 할 때 logn.전체적인 시간 복잡 도 는 O (n + k * logn) 이다. 이런 방법 은 2 와 비교 하면 시간 복잡 도가 작 지만 공간 복잡 도 는 O (n) 이 고 가장 많은 공간 복잡 도 는 O (k) 7 이다. 사고 방향 은 6 과 같다. 단지 지붕 요 소 를 다 뽑 은 후에 다시 배열 할 때 지붕 으로 바 꾸 는 요 소 는 최대 k 번 아래로 이동 하면 충분 하 다.이때 쌓 아 올 린 요 소 는 우리 가 찾 아야 할 두 번 째 작은 요소 이다. 그 다음 에 두 번 째 작은 요 소 를 꺼 내 서 다시 쌓 아 올 린 마지막 요 소 를 쌓 아 올 린 다음 에 k - 1 번 아래로 이동 한 후에 아래로 이동 하 는 횟수 가 점점 줄 어 들 었 다. k - 1 번 반복 하면 서 계속 꺼 내 는 쌓 아 올 린 요 소 는 우리 가 찾 아야 할 가장 작은 k 갯 수 이다. 그러나 주의해 야 한다.알고리즘 이 중 단 된 후의 더 이상 최소 더미 가 아 닙 니 다. 사고 6 에서 추출 할 때마다 logn 이 필요 합 니 다. 이것 은 k 가 필요 합 니 다. 전체적인 시간 복잡 도 는 O (n + k ^ 2) 입 니 다.
이루어지다
코드 는 모두 컴 파일 디 버 깅 을 통 해 기록 이 편리 한 후에 다시 고 개 를 돌려 복습 하지만 느낌 은 비교적 낮은 것 같다.힘 내세 요.사고방식 1: 빠 른 정렬

/************************************************************************* > File Name: quicksort_kmin.cpp > Author: zxl > mail: [email protected] > Created Time: 2016 04 07      21 01 26  ************************************************************************/

#include <iostream>
#define MAX 20000
#define K 100
using namespace std;
int partion(int A[],int start,int end)
{
    int x = A[end];
    int i = start-1;
    int j;
    for(j = start;j<end;j++)
    {
        if(A[j] <= x)
        {
            i++;
            swap(A[i],A[j]);

        }

    }
    swap(A[i+1],A[end]);
    return i+1;

}
void quicksort(int A[],int start,int end)
{
    if(start < end)
    {
        int mid = partion(A,start,end);
        quicksort(A,start,mid-1);
        quicksort(A,mid+1,end);
    }
}
void Kmin(int A[],int length,int k)
{
    int i;
    quicksort(A,0,length);
    for(i = 0;i<k;i++)
    {
        cout << A[i] << endl;
    }

}
int main()
{
    int A[MAX];
    int i;
    for(i = 0;i< MAX;i++)
        A[i] = MAX-i;
    Kmin(A,MAX-1,K);
    return 0;
}

사고방식 2:

/*************************************************************************
    > File Name: kmin_2.cpp
    > Author: zxl
  > mail: 857317335@qq.com
    > Created Time: 2016 04 07      22 12 24 
 ************************************************************************/

#include <iostream>
#define MAX 200
#define K 10
using namespace std;
void swap(int * a,int *b)//c++    swap  
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}
//           
int FindMax(int buf[],int length)
{
    int i;
    for(i = 0;i<length;i++)
    {
        if(buf[i] > buf[length-1])
        {
            swap(buf+length-1,buf+i);
        }
    }
    return buf[length-1];
}
void Kmin(int A[],int length,int k)
{
    int B[k];
    int i;
    int max;
    for(i = 0;i<k;i++)
    {
        B[i] = A[i];
    }
    max = FindMax(B,k);
    for(i = length-k-1;i<length;i++)
    {
        if(A[i] >= max)
            continue;
        else
        {
            swap(B+k-1,A+i);
            max = FindMax(B,k);

        }
    }
    for(i = 0;i< k;i++)
        cout << B[i] << endl;

}
int main(void)
{
    int A[MAX];
    int i;
    for(i=0;i< MAX;i++)
        A[i] = MAX-i;
    Kmin(A,MAX,K);
    return 0;
}

사고 3: k 개 요소 의 최대 더 미 를 유지 하고 대량의 데 이 터 를 처리 하 는 데 적용 합 니 다.

/************************************************************************* > File Name: kmin_3.cpp > Author: zxl > mail: [email protected] > Created Time: 2016 04 08      15 11 55  ************************************************************************/

#include <iostream>
#define MAX 10
#define K 3
using namespace std;

int Parent(int i)
{
    return i/2;
}
int LEFT(int i)
{
    return i*2;
}
int RIGHT(int i)
{
    return 2*i+1;
}
void Max_heapify(int A[],int size,int i)
{

    int l = LEFT(i);
    int r = RIGHT(i);
    int largest;
    if(l <= size && A[l]> A[i])
        largest = l;
    else
        largest = i;
    if(r<= size && A[r] > A[largest])
        largest = r;
    if(largest != i)
    {
        swap(A[i],A[largest]);
        Max_heapify(A,size,largest);
    }

}
void Build_Max_heap(int A[],int size)
{ 
    int i;
    for(i = size/2;i>0;i--)
        Max_heapify(A,size,i);
}
void Kmin(int A[],int length,int k)
{
    int i,j;
    int B[k];
    for(i = 1;i<= k;i++)
        B[i] = A[i];
    Build_Max_heap(B,k);

    for(j = k+1;j<=length;j++)
    {
        if(A[j] > B[1])
            continue;
        else
        {
            swap(A[j],B[1]);
            Max_heapify(B,k,1);
        }
    }
    for(i = 1;i<=k;i++)
        cout << B[i] << endl;

}
int main()
{
    int A[MAX];
    int i;
    for(i = 1;i<=MAX;i++)
    {
        A[i]= MAX-i;
    }
    Kmin(A,MAX,K);
    return 0;
}

사고 4: 중추 원 을 선택 할 때 세 가지 중간 값 법 을 사용 하고 빠 른 선택 은 두 번 이 아니 라 한 번 만 재 귀 호출 을 하면 평균 시간 이 O (N) 임 을 보장 할 수 있다.

/*************************************************************************
 > File Name: kmin_4.cpp
 > Author: zxl
 > mail: 857317335@qq.com
 > Created Time: 2016 04 11      09 48 33 
 ************************************************************************/

#include <iostream>
#define CTUOF 3
#define MAX 100
#define K 30
using namespace std;
//         
/* A[left],A[right],A[center]  ，      A[left],    A[right],      A[right-1]，       i j    left+1, right-2。
*/
int Median3(int A[],int left ,int right)
{
    int center = (left + right)/2;
    if(A[left] > A[center])
        swap(A[left],A[center]);
    if(A[left] > A[right])
        swap(A[left],A[right]);
    if(A[center] > A[right])
        swap(A[center],A[right]);
    swap(A[center],A[right -1]);
    return A[right-1];
}
void Insertsort(int A[],int N)
{
    int i,j;
    int temp;
    for(i = 1;i < N;i++)
    {
        temp = A[i];
        for(j = i;j > 0 && A[j-1] > temp;j--)
            A[j] = A[j-1];
        A[j] = temp;
    }


}
void Qselect(int A[],int k ,int left ,int right)
{
    int i,j;
    int pivot;
    if(left + CTUOF <= right)
    {
        i = left;
        j = right-1;
        pivot = Median3(A,left,right);
        while(true)
        {
            while(A[++i] < pivot) {}
            while(A[--j] > pivot) {}
            if(i <j)
                swap(A[i],A[j]);
            else
                break;
        }
        swap(A[i],A[right-1]);
        if(k <=i)
            Qselect(A,k,left,i-1);
        else if(k > i+1)
            Qselect(A,k,i+1,right);

    }
    else
        Insertsort(A+left,right-left+1);
}
int main()
{
    int i;
    int A[MAX];
    for(i = 0;i< MAX;i++)
        A[i] = MAX-i;
    Qselect(A,K,0,MAX-1);
    for(i = 0;i<K ;i++)
        cout << A[i] << endl;
}

사고방식 4 의 2: 알고리즘 서론 P120 에서 나 온 것 으로 선형 시간의 선택 알고리즘 을 기대 하고 운행 시간 은 O (N) 이다.중추 원 은 무 작위 선택 이다.

/************************************************************************* > File Name: kmin_4_2.cpp > Author: zxl > mail: [email protected] > Created Time: 2016 04 11      15 56 16  ************************************************************************/

#include <iostream>
#include <stdlib.h>
#include <time.h>
#define MAX 1000
#define K 10
using namespace std;
int random(int a,int b)
{
    srand((unsigned)time(NULL));
    return (rand() %(b-a+1))+a;

}
int Partion(int A[],int start,int end)
{
    int x = A[end];
    int i,j;
    i = start-1;
    for(j = start;j< end;j++)
    {
        if(A[j]<= x)
        {
            i++;
            swap(A[i],A[j]);
        }

    }
    swap(A[i+1],A[end]);
    return i+1;
}
int RandomPartion(int A[],int start,int end)
{
    int i;
    i = random(start,end);
    swap(A[end],A[i]);
    return Partion(A,start,end);

}
void RandomSelect(int A[],int start,int end,int k)
{
    if(start == end)
        return;
    int q;
    q = RandomPartion(A,start,end);
    int cout = q-start+1; //     ；
    if(cout == k)
        return;
    else if(k < cout)
        RandomSelect(A,start,q-1,k);
    else
        RandomSelect(A,q+1,end,k-cout);

}
int main()
{
    int A[MAX];
    int i;
    for(i = 0;i<MAX;i++)
        A[i] = MAX-i;
    RandomSelect(A,0,MAX-1,K);
    for(i = 0;i< K;i++)
        cout << A[i] << endl;
    return 0;
}

사고 5: 선형 시간 정렬, 계수 정렬, O (N), 그러나 제한 이 비교적 많 고 자주 사용 되 지 않 습 니 다.

/*************************************************************************
 > File Name: kmin_5.cpp
 > Author: zxl
  > mail: [email protected]
 > Created Time: 2016 04 11      16 41 54 
 ************************************************************************/

#include <iostream>
#define MAX 1000
#define K 10
using namespace std;
void cout_sort(int A[],int length,int k)
{
 int B[length];
 int C[length];
 int i,j;
 for(i = 0;i<length;i++) //    c      ，       max，    。
 C[i] = 0;
 for(j = 1;j<=length;j++)
 C[A[j]] = C[A[j]]+1;
 for(i = 0;i<length;i++)
 C[i] = C[i-1]+ C[i];
 for(j = length;j>1;j-- )
 {
 B[C[A[j]]] = A[j];
 C[A[j]] = C[A[j]]-1;
 }
 for(i = 1;i<=k;i++)
 cout << B[i] << endl;

}
int main(void)
{
 int A[MAX];
 int i;
 for(i = 1;i<= MAX;i++)
 A[i] = MAX-i;
 cout_sort(A,MAX,K);
 return 0;
}

사고방식 6: 최소 더미 정렬 을 한 다음 에 순서대로 더미 요 소 를 꺼낸다.

/************************************************************************* > File Name: kmin_6.cpp > Author: zxl > mail: [email protected] > Created Time: 2016 04 11      17 07 33  ************************************************************************/

#include <iostream>
#define MAX 1000
#define K 10
using namespace std;

int LEFT(int i)
{
    return 2*i;
}
int RIGHT(int i)
{
    return 2*i+1;
}
void Min_heapify(int A[],int size,int i)
{
    int l = LEFT(i);
    int r = RIGHT(i);
    int small;
    if(l <= size && A[l] < A[i])
        small = l;
    else
        small = i;
    if(r <= size && A[r] < A[small])
        small = r;
    if(small != i)
    {
        swap(A[i],A[small]);
        Min_heapify(A,size,small);
    }
}
void Build_Min_heap(int A[],int size)
{
    int i;
    for(i = size/2;i> 0;i--)
    {
        Min_heapify(A,size,i);
    }
}
void Kmin(int A[],int size,int k)
{
    Build_Min_heap(A,size);
    int i;
    int length = size;
    for(i = length;i>length-k;i--)
    {
        swap(A[1],A[i]);
        cout << A[i] << endl;
        size = size-1;
        Min_heapify(A,size,1);
    }
}
int main(void)
{
    int A[MAX];
    int i;
    for(i = 0;i< MAX;i++)
        A[i] = MAX-i;
    Kmin(A,MAX,K);
    return 0;
}