(basic) 시/공간 복잡도, 빅오(big-O), 트리, 정렬 알고리즘(코드포함)

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

- 시간복잡도란?

- 공간복잡도란?

- Big-O는 어떻게 표현하는가?

- 트리란?

- 힙트리 코드구현

- 정렬의 종류와 시간복잡도

- 정렬 알고리즘의 코드(c++)

- 퀵정렬 vs 힙정렬

- 비트연산자와 시프트(shift)연산자의 의미

- 재귀 호출(recursive call)이란 무엇이고 왜 사용하나?

 

 

 

 

- 시간복잡도란

big-O에서의 개념이다.

시간복잡도는 알고리즘의 수행시간이 얼마인지를 나타내는것이다.

 

 

- 공간복잡도란

메모리를 얼마나 잡아 먹느냐에 따른건데

제한된 메모리의 영역(임베디드, 펌웨어 하드웨어등)에서의 코딩할때는 중요하다.

하지만 요새는 기술이 워낙발전하여서 공간복잡도를 크게 따지지는 않을것이라 생각된다.

왜냐하면 시간복잡도가 좋을수록 메모리를 많이 차지하는 경향이 매우 적기 때문이다.

단순히 말해 시간복잡도가 증가할수록 공간복잡도 또한 증가하는 경향이 크다.

 

 

- Big-O는 어떻게 표현하는가?

big-O는 O(n), O(1), O(n^2) ... 등 과같이 표시한다.

n의 개수는 무한하다고 가정한다.(n의 개수가 최소일때는 오메가를 사용한 표기로 한다(이제 사용안함))

O(2n) -> o(n)

O(n+1) -> O(n)

O(n^2 + n) -> O(n^2) ...

등 상수같은 작은값들은 무시해버린다. 최고차항이 무엇인지가 중요하며 영향력이 부족한 수는 제거하여 표시한다.

왜냐하면 n의 무한으로 갈경우 무시해도되는숫자이기 때문이다.

속도는 다음과 같다.

 

수행시간 : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

O(1)의 최고의 성능이며 O(n^n)은 최악의 성능이다.

예를들어 O(1)은 스택에서 O(2^n)은 피보나치 수열에서 사용된다

 

그리고 O(n^2)을 다시한번 해석하자면

1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다.

(1만개 > 10만개 에는 10배가 늘어났지만 시간은 ^2하여서 100배가 늘어난다).

 

- 트리란?

 

완전이진트리 : 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리 (순서대로 삽입한다고 생각하면됨)

트리는 부모가 자식보다 크다는것이 중요하지 자식의 왼쪽이 크냐 오른쪽이 크냐는 중요하치않다.

 

- 힙트리 코드구현

 

이것을 기본으로 힙정렬을 이해해야함. 힙트리를 코드로 구현하지 못한다면 힙정렬 코드를 이해하지못한다.

이진트리를 트리로 구현할때에는 다음 사항을 기억해야한다.

힙 코드에 삽입을 하는과정은 다음과 같다.

힙코드를 삭제할 때는 다음과같다.

1. 맨위의 값이 최대값이므로 루트노드를 삭제

2. 최하단 노드의 오른쪽 끝을 루트노드로 옮김

3. 루트노드는 최대값이여하니까 자식들과 비교하여 가장 큰값을 루트노드로 옮김

4. 그다음에 또 자식들이랑 비교하여 이동 ... 이동 ... 이동 ...

5. 결국에는 다시 최대값이 루트노드에 있는 힙이 만들어짐(원상태로)

 

코드는 여기있어요.

from : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

// 최대 힙(max heap) 삭제 함수
element delete_max_heap(HeapType *h){
  int parent, child;
  element item, temp;

  item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당
  temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 힙 크기를 하나 감소
  parent = 1;
  child = 2;

  while(child <= h->heap_size){
    // 현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
    if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
      child++;
    }
    // 더 큰 자식 노드보다 마지막 노드가 크면, while문 중지
    if( temp.key >= h->heap[child].key ){
      break;
    }

    // 더 큰 자식 노드보다 마지막 노드가 작으면, 부모 노드와 더 큰 자식 노드를 교환
    h->heap[parent] = h->heap[child];
    // 한 단계 아래로 이동
    parent = child;
    child *= 2;
  }

  // 마지막 노드를 재구성한 위치에 삽입
  h->heap[parent] = temp;
  // 최댓값(루트 노드 값)을 반환
  return item;
}
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

heap코드는 넣는거는 코드가 일관된데 삭제하는부분에서는 개발자마다 너무 갈리고 복잡해지는것같아서

제일 간단하고 심플해보이는 코드로 가져왔다.

 

아마 element는 struct를 #define으로 하신것같습니다. 그러니까 element는 struct 구조체인것 같습니다.

그냥 int라고 생각하면 편하다

 

1. temp에다가 가장 마지막 노드를 저장하고

2. 왼쪽자식이랑 오른쪽자식이랑 큰거를 비교하여서 오른쪽이 크면 child++ 아니면 그대로

3. 큰쪽이랑 temp.key(마지막노드(struct로 접근할때는 요런식임))랑 비교하여 temp.key가 크면 끝내고

아니라면 비교후 변경(h -> heap[parent] = h -> heap[child])

( h -> heap[parent] 는 위에다가 저장했으니 상관없다.)

4. 부모를 자식으로 바꾸고 자식은 다시 부모의*2

 

이것을 반복하는데 언제까지하느냐? --->  child를 계속 *2 하다보면 힙 사이즈보다 작거나 같을때까지만한다.

 

생각보다 이해하는데 어려웠던게 직접 구현하면 금방하는데 남의 코드 이해할려니까 어려웠다.

 

- 정렬의 종류와 시간복잡도

 

동영상부터 감상

알고리즘 시각화 테스트 가능한 사이트

Sorting Algorithms Animations

 

 

1. 선택정렬(Selection Sort)

 GIF를 보면 알겠지만 그냥 순서대로 하는것이다.

아주 간단하게 왼쪽부터 순서대로 차근차근 비교하면서 넣는것이다.

평균적으로 O(n^2)로 느린편이다.

 

 

2. 삽입정렬(Insertion Sort)

 

 선택정렬과의 차이라고하면 선택정렬은 선택한 두개만 딱 교환해주는것이고

삽입정렬은 바로 다음거를 바로바로 삽입할 공간을 만들어주면서 삽입해주는것이다.

삽입할 공간을 만들어준다는것이 포인트이다.

배열이 작을경우 최고의 효율을 보이고 구현도 매우쉽다.

또한 정렬이 되어있는 자료구조에서의 삽입/삭제시 최고의 알고리즘이다.

O(n^2)중에서 빠른편이다.

 

 

3. 힙 정렬(heap Sort)

O(nlogn) 정렬의 성능을 발휘하는 장점을 가지고있고

선택정렬(Selection Sort)와 똑같은 알고리즘이다. 하지만 가장큰 원소를 뒤로 먼저 보내는 포인트에서 차이가있다.

1. 값들을 전부 힙트리에다가 삽입하고 삽입도중에는 큰값이 항상 위쪽에 오게 하며

2. 오른쪽아래부터 순서대로 층을올라간다.

3. 최하단 오른쪽값을 최상단값을 바꾸고 최상단이였던값은 맨오른쪽 끝으로 보낸다.

4. 그리고 최하단 오른쪽값이였다가 최상단으로간값은 다시 아래쪽 큰수랑 비교하면서 바꾸고나서

5. 다시 위와같은것을 반복한다.

 

O(nlogn)이라서 quick sort과 똑같지만 캐시친화도(얼마나 메모리 사이가 가까이있나의 차이)에 의해서

quick sort 더 빠르다고 한다. 하지만 항상 일정한 성능을 발휘한다. 그래서 퀵정렬 알고리즘이 최적화가 안되있을때는 이거를 사용하는것이낫다

 

 

4. 버블정렬(Bubble Sort)

 거의 모든 상황에서 최악의 성능을 보여주는 정렬 알고리즘이다.

단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다

가장 쉬운 알고리즘이나 최악이기 때문에 무조건 지양해야 하는 알고리즘이다.

O(n^2)이고 실제개발에서 절대 쓰일일 없는 알고리즘이다.

 

 

5. 합병정렬(Merge Sort)

 데이터의 상태에 별영향을 안받는 알고리즘이다.

존포이노만이 개발한 알고리즘이다.

맨위 sorting algoriths in 6minutes 영상에 1:06에 나온다.

사실 이해가 잘 가지 않아서

https://zeddios.tistory.com/38

합병정렬(Merge Sort) 알고리즘 정리 ( 개념 / 시간복잡도 - O(nlogn) )

해당 블로그에 설명이 아주아주 잘되어있다.

 

 

 

6. 퀵 정렬(Quick Sort)

partition step을 사용하는것을 의미하며 피벗(pivot)을 잡고 크면 오른쪽 작으면 왼쪽으로 나누는것이다.

퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다.

대체적으로 빠르다는얘기다. 하지만 최적화 작업을 하지 않을경우 그다지 뛰어난 성능을 발휘하지는못한다.

왜냐하면 최악의 경우 O(n^2)이기 때문이다.

 

- 정렬 알고리즘의 코드(c++)

1. 선택 정렬(Selection sort) 코드

#include <algorithm>

using namespace std;

void selection(int *array, int begin, int end)
{
    for (int i = begin; i < end; ++i)
    {
        int imin = i;
        for (int j = i + 1; j <= end; ++j)
        {
            if (array[imin] > array[j]) imin = j;
        }
        if (imin != i) swap(array[i], array[imin]);
    }
}

코드 설명 : 

2. 삽입정렬(Insertion sort) 코드

void insertion(int *array, int begin, int end)
{
	for (int i = begin + 1; i <= end; i++)
	{
		int j, v = array[i];
		for (j = i; j > begin && array[j - 1] > v; j--)
			array[j] = array[j - 1];
		if (i != j) array[j] = v;
	}
}

코드 설명 : 

3. 힙정렬(heap sort) 코드

 

https://github.com/jjkyun/sorting/tree/master/sorting_1

jjkyun님의 github의 heapsort.c 에 있다.

void heapify(int* arr, int size, int mid){
    int parent_node = mid; // parent node index
    int left_node = parent_node*2+1; // left child node index
    int right_node = parent_node*2+2; // right child node index
    int largest_node = parent_node;
    int temp;
    
    // Check if left child exists && compare the value
    if(left_node < size && arr[left_node] > arr[largest_node]){
        largest_node = left_node;    
    }
    // Check if right child exists && compare the value
    if(right_node < size && arr[right_node] > arr[largest_node]){
        largest_node = right_node;    
    }
    // Swap
    if(parent_node != largest_node){
        temp = arr[largest_node];
        arr[largest_node] = arr[parent_node];
        arr[parent_node] = temp;
        // if swap happened then heapify again
        heapify(arr, size, largest_node);
    }


}

// build heap heap tree
void buildMaxHeap(int* arr, int size)
{   
    // start from middle node (index starting from 0)
    int mid = size/2-1;
    
    // loop until root node 
    for(mid; mid>=0; mid--){
        heapify(arr, size, mid);
    }
}

/*
Heapsort Algorithm
1. Build heap tree (max, min)
2. Sort by reconstructing the 1. heap tree
*/ 
void heapSort(int* arr, int size)
{
    buildMaxHeap(arr, size);
    
    // Swap root node with last node
    // loop until the heap tree size goes to 1
    int temp;
    while(size > 1){
        temp = arr[0];
        arr[0] = arr[size-1];
        arr[size-1] = temp;
        
        size--;
        heapify(arr, size, 0);
    }

}

코드 설명전 이해가 필요한 항목 : 

heapify() 함수에 대한설명

: heapify()는 최하단 노드부터 살펴보면서 최대값을 찾아 최상단으로 끌어올려주는 역할을함

 

 

 

4. 버블정렬(Bubble sort) 코드

#include <algorithm>

using namespace std;

void bubble(int *array, int begin, int end)
{
    for (int i = end; i > begin; --i)
    {
        bool isdone = true;
        int j;
        for (j = begin; j < i; ++j)
        {
            if (array[j] > array[j + 1])
            {
                isdone=false;
                swap(array[j], array[j + 1]);
            }
        }
        if(isdone == true) break;
    }
}

1. 왼쪽부터 두개씩 비교해서 맨끝에다가 큰값을 넣음

2. 그다음 맨끝앞에 큰값을 넣음

3.....

..

n개의 개수를 비교할때 다음과 같이 비교한다. 제일로 쉬운 정렬 알고리즘이다.

for (int i = 0; i < COUNT - 1; i++)
    {
        for (int j = 0; j < COUNT - 1 - i; j++)
        {
            if (data[j] > data[j + 1])
            {
                temp        = data[j];
                data[j]     = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }

 

 

5. 병합/합병정렬(Merge sort) 코드

 

참고한 링크

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

# include <stdio.h>
# define MAX_SIZE 8
int sorted[MAX_SIZE] // 추가적인 공간이 필요

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){
    if(list[i]<=list[j])
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  // 남아 있는 값들을 일괄 복사
  if(i>mid){
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];
  }
  // 남아 있는 값들을 일괄 복사
  else{
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
    mid = (left+right)/2 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {21, 10, 12, 20, 25, 13, 15, 22};

  // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
  merge_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

분할(Divide) -> 정복(Conquer) -> 결합(Combine) 순서대로 진행되며

정복과 결합을 끝날때까지 반복된다.

전체를 리스트가 1이 될때까지 분할시키고 그다음에는

1 -> 2 -> 4 -> 8 로 진행되면서 정복과 결합이 진행된다.

main에서는 list로 받은것을 merge_sort에 넘겨준다.

merge_sort에서 받은 list를 다시금 merge_sort로 넘겨주는 재귀호출(recursive call)로 진행하며

리스트를 순서대로 진행하다보면 왜 이렇게 되나 알수있는데

코드를 보고 순식간에 이렇게 진행되는것을 이해하기란 어렵다.

단순히 큰 흐름을 파악해보고 따져보면 결국에는 리스트가 1이 될때까지

왼쪽을 담당하는 merge_sort(list, left, mid) 와 오른쪽으로 담당하는 merge_sort(list, mid+1, right)가 반복적으로

들어가면 리스트 1이 되면 -> if(left<right)가 성립이 안되 더이상 진행이 안되며 그때부터 

merge가 작동하여서 list를 채워놓는다.

 

merge()에 들어가서는 다음코드를 순서대로 해석해본다.

오름차순으로 정렬해주는것이다.

1. 왼쪽부분과 오른쪽부분을 비교하여서 작은쪽은 sorted[]에 넣는다.

2. 그리고 큰쪽은 남아서 다음비교대상이 되고 작은쪽이 사라진자리는 ++ 하여서 그다음항을 비교한다.

3. 그리하여서 &&으로 동시에 만족하지못할결우( i 또는 j가 mid와 right를 넘어갈경우 끝낸다) 끝낸다.

 

그리고 끝나면 i가 mid보다 크다면( 크다는뜻은 i가 값이 j쪽보다 전부작아서 먼저 종료된경우)

그리고 그 반대의 경우 반대편에 있는 나머지를 전부 sorted[]에 복사해준다.

 

 

끝나면 sorted에 있는것을 다시 list에 넣어서 다시금 배열을 진행할수있게끔 한다.

솔직히 설명으로는 이해하기 힘들고 생각을 하나하나 예시를 들어서 인내하여 해보면 이해하기 쉽다.

시간이 조금 걸리더라도 전체적인 흐름을 파악하고 나아가며 이해해야한다.

 

 

6. 퀵 정렬(Quick sort) 코드

 

[C] Quicksort:: 퀵정렬

 

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int pivot = arr[(left + right) / 2];
      int temp;
      do
      {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i<= j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
      } while (i<= j);

    /* recursion */
    if (left < j)
        quickSort(arr, left, j);

    if (i < right)
        quickSort(arr, i, right);
}

단순히 이것을 무한반복하면 된다.

: j를 1씩 증가시키며 j의 자리에 있는 값이 피벗 값보다 크면 아무 조치를 하지 않고

j의 자리에 있는 값이 피벗 값보다 작으면 i를 1 증가 시키고 swap 한다.

 

 

이것으로 이해가 안갈경우

 

위키피디아 예제 항목 살펴보길바람

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC#C++

퀵 정렬 - 위키백과, 우리 모두의 백과사전

 

c언어 코드

(가운데에 pivot을 넣고 양쪽에서 left++ right-- 하면 확인하는코드)

 

c++코드

내가 위에 그림으로 그리면서 설명한것을 코드로 바꾼것

왜 굳이 j를 기준으로 i를 -1하였는지는 모르지만

i = low, j = low+1로 해도 상관없을듯함

 

- 퀵정렬 vs 힙정렬

 

퀵정렬이 힙정렬보다 대체적으로 시간복잡도로 따졌을경우 최악의 경우에서 더 느려보이지만

힙정렬은 힙을 구성하는데 시간(swap사용)이 오래걸려서 퀵정렬이 대체적으로 더 빠르다.

이미 힙이 구성된 배열에서는 힙정렬이 퀵정렬보다 더 빠르다.

 

하지만 위와 같은 논의의 필요성은 크게 타당하지 않다는 의견이 많다.

왜냐하면 힙정렬을 쓰는이유는 정렬을 유지하며 데이터의 추가,삭제가 매우 빠르기 때문이다.

유지적인 측면에서 힙정렬을 사용하는것이다.

 

힙정렬은 퀵정렬처럼 한번 툭 쓰고 마려는 목적으로 쓰는것이 아니다.

그러므로 위와 같은 논의가 크게 필요하지 않다는 의견이 많다.

 

 

 

 

 

- 비트연산자와 시프트(shift)연산자의 의미

 

shift 연산자의 의미 :  << n  ==> *2^n   , >> n ==> /2^n

비트연산자로 짝수 홀수 구분 :   

만약 n | 1 ==> n+1 라면 n은 짝수이고 결과값이 그대로 n이라면 홀수

반대로말해 n이 짝수이면 +1 더하여 홀수로 만들고 홀수면 그대로 두어라

만약 n & 1 ==> 0 라면 n은 짝수 1이라면 홀수이다.

 

- 재귀 호출(recursive call)이란 무엇이고 왜 사용하나?

 

재귀 호출은 예를들어 다음과 같은 형태로 되어있다.

 

int sum(int a, int b){

      return sum(a+b,b);

}

 

쉽게말해 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위를 의미한다.

사용하는 이유는 코드의 직관성과 간결함을 위해서 사용되나

성능이 떨어지며 (성능상의 문제) 무한 재귀함수호출의 위험성을 가지고 있다.