[자료구조 - C언어] 자료구조 제19강: 시간복잡도와 점근적 분석(2), (3)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 검색

• 검색: 원하는 데이터가 있는지 없는지를 찾고, 있으면 어디 있는지를 찾는 것
• 1차원 list로 한정할 때
  • 순차 검색(sequential Search)
    • 는 순차적으로 하나 하나 비교하며 검색하는 것으로 O(n)의 시간 복잡도를 가진다.
    • 배열과 연결리스트 모두에서 사용할 수 있다.
  • 이진 검색(Binary Search)
    • 2. 이진 검색
    • 배열만 사용할 수 있다.

 

2. 이진 검색(Binary Search)

• 배열에 데이터들이 내림/오름차순으로 정렬되어 있어야 한다.
• first, last, middle=(first+last/2)로 중간값과 target의 값을 비교하여 검색 범위를 좁혀 나간다.
  • 중앙값 < target → first = middle + 1
  • 중앙값 > target → end = middle -1
  • 범위를 좁혀나갈 때 first > last 인 경우는 찾을 범위가 없다는 뜻으로 찾는 값이 존재하지 않아 종료한다.

int binarySearch(int n, char *data[], char *target){
    int first = 0, last = n-1;
    while(first <= last){    //적어도 찾을 구간이 남아있는 동안은
        int middle = (first + last) / 2; //완전 정확한 위치일 필요 X ~ 3.5라면 3으로
        int result = strcmp(data[middle], target);
        if(result == 0)    //찾았을 경우
            return middle;
        else if(result < 0) //target이 더 크다 = 더 뒤에 있다
            first = middle + 1;
        else
            last = middle - 1;
    }
    return -1;
}

• 한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어든다. ⇒ 시간 복잡도는 O(log2n)이다.

2-1. 순차 검색과 이진 검색의 시간 복잡도

• 순차 검색의 시간 복잡도는 O(n)
• 이진 검색의 시간 복잡도는 O(log2n)
• 둘의 차이는 매우 크다
  • 영어 사전을 1쪽부터 순차적으로 찾는 것(=순차 검색)과 중간을 펴가며 범위를 좁히는 것(= 이진 검색)은 다르다!
  • 그러나, 이진 검색은 이미 정렬되어 있어야 한다. ~ 그렇기 때문에 이진 검색을 할 수 있는 상황에서 순차 검색은 👎

2-2. 연결 리스트와 검색

• 순차 검색의 경우는 배열과 연결 리스트 모두에서 가능하다.
• 하지만 이진 검색의 경우
  • 연결 리스트는 랜덤 액세스가 불가능하다.
    • 그렇기 때문에 가운데(middle) 데이터를 O(1) 시간에 읽을 수 없다.
    • 따라서 이진 검색을 할 수 없다.

 

3. 버블 정렬(Bubble Sort)

void bubbleSort(int data[], int n){
    for(int i=n-1; i>0; i++){
        for(in tj=0; j<i;j++){
            if(data[j]>data[i]){
                int tmp = data[j];
                data[j] = data[i];
                data[i] = tmp;
            }
        }
    }
}

• = (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n^2)
• 데이터의 개수가 동일하다면 항상 동일한 횟수만큼 실행한다. ⇒ 항상 O(n^2)의 시간 복잡도를 가진다.

 

4. 삽입 정렬(Insertion Sort)

• data[i]를 data[0] ~ data[i-1]의 범위에서 제 자리를 찾아 삽입하는 알고리즘

void insertion_sort(int nn, int data[]){
    for(int i=1; i<n; i++){
        int tmp = data[i];
        int j = i-1;
        while(j>=0 && data[j] > tmp){
            data[j+1] = data[j];    //shift
            j--;
        }
        data[j+1] = tmp;
    }
}

• 최선의 경우: 다 정렬되어 있어서 내부의 while문을 1번만 실행하게 되는 경우 ⇒ O(n)
• 최악의 경우: 거꾸로 정렬되어 있어 내부의 while문을 n번 실행하게 되는 경우 ⇒ O(n^2)
• 일반적으로 버블 정렬보다 삽입 정렬이 2배 정도 빠르다.

 

5. 다른 정렬 알고리즘

• 퀵 소트(quick sort) 알고리즘: 기준값을 선정해 해당 값 보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬
  • 최악의 경우 O(n^2)
  • 평균 시간 복잡도는 O(nlog2n)
• 최악의 경우 O(nlog2n)의 시간 복잡도를 갖는 정렬 알고리즘
  • 합병 정렬(merge sort): 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
  • 힙 정렬(heap sort): 힙이라는 특수한 자료구조를 사용하는 정렬 알고리즘
    • 최소힙: 루트 노드에는 최솟값, 최소힙의 각 노드의 값은 자신의 자식 값 보다 작다.
    • 최대힙: 루트 노드에는 최댓값, 최대힙의 각 노드의 값은 자신의 자식 값 보다 크다.
• 데이터가 배열이 아닌 연결 리스트에 저장되어 있다면?
  • n^2의 시간을 벗어나기 어려움

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/ZX2mC6OJrqM

https://youtu.be/p0cC6sZg3OI