자료구조 2장 - 정렬, 탐색, 재귀, 순열 그리고 복잡도에 대해서

정렬

- 선택 정렬

void sort(int* a, const int n) {
    // n개의 정수 a[0]부터 a[n-1]까지 비감소순 정렬
    for (int i = 0; i < n; i++) {
        int j = i;
        //a[i]와 a[n-1]사이에 가장 작은 정수 값을 찾음
        for (int k = i + 1; k < n; k++) {
            if (a[k] < a[j]) {
                j = k; // 교환
            }
        }
        swap(a[i], a[j]);
    }
}

제일 작은 정수를 찾아 앞으로 보내는 작업을 계속 반복한다.

​

탐색

이원탐색(binary search)

int binarySearch (int arr[], int low, int high, int key) {
  while (low <= high) {
    int mid = low + (high-low) / 2;
    
    if (arr[mid] == key) // 종료 조건1 검색 성공.
      return mid; 
    else if (arr[mid] > key) 
      high = mid - 1;      
    else 
      low = mid + 1;
  }
  return -1 ; // 종료 조건2 (low > high) 검색 실패.
}

low,high = 각각 배열 arr의 왼쪽, 오른쪽 끝 지점

mid를 배열의 가운데 인덱스로 정해주고,

찾고자 하는 key가 mid보다 크면, low를 mid + 1로 / 반대로 작다면 high를 mid-1로 설정해주어 범위를 좁혀나간다.

​

재귀

int FACT(int N){
    if(N==0){
        return(1); // 재귀함수의 종료조건
    }
    else{
        return(N*FACT(N-1));
    }
}

재귀 : 자기 자신을 다시 호출

위 코드의 호출 순서 : N! = N*(N-1)! = N*(N-1)*(N-2)*...*2*1*1

​

효율적일 수 있으나, 순환을 위한 준비 설정이 필요하다.

​

순열

void perm(char *a, const int k, const int m) {
    // a[k]...a[m]에 대한 모든 순열 생성
    if (k == m) {
        for (int i = 0; i <= m; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    else { // a[k]...a[m]에 있는 여러 순열을 재귀적으로 생성
        for (int i = k; i <= m; i++) {
            // a[k] <-> a[i]
            swap(a[k], a[i]);
            // a[k+1],...,a[m-1]에 대한 모든 순열 생성
            perm(a, k + 1, m);
            // 원래 상태로 되돌리기 위해 a[k] <-> a[i]
            swap(a[k], a[i]);
        }
    }
}

C++ 표준 템플릿 라이브러리 STL를 이용하면 next_permutation함수를 통해 손쉽게 순열을 얻을 수 있다.

​

성능분석

크게 공간 복잡도(필요한 공간의 양)와 시간 복잡도(필요한 시간의 양)으로 나눌 수 있다.

​

공간 복잡도

공간복잡도는 RAM이나 메모리가 얼마나 필요한가를 표기하는 것입니다. 공간복잡도도 빅오, 빅오메가, 빅세타로 표기할수 있으며, 시간복잡도와 다른 점은 단지 시간관점인가 공간관점인가의 차이

시간 복잡도

1. 빅 오

최악의 경우 라고도 함

2. 오메가

빅 오메가는 빅 오와는 반대되는 개념입니다. 대개 최선의 경우

3. 세타

빅 오와 빅 오메가의 공통부분입니다. 최소와 최악의 중간인 평균적인 복잡도

빅 오 표기법이 제일 흔히 사용된다.

-> 최악의 경우를 말하는 것이 더 신뢰도가 높기 때문.