[자료구조] 자료구조에 이해 - 시간 복잡도(Time Complexity) , 공간 복잡도(Space Complexity)

자료구조에 이해

자료구조(資料構造, 영어: data structure)는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. 

 

자료구조 분류

자료구조는 크게 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 대 1인 선형 구조, 1 대 다 혹은 다 대 다 구조인 비선형 구조,

마지막으로 파일 구조가 있습니다.

 

[구현]

배열  , 튜플  , 연결 리스트 , 환형 연결 리스트 , 이중 연결 리스트 , 환형 이중 연결 리스트 , 해시 테이블

 

[형태]

선형 구조 - 스택 , 큐  , 환형 큐  , 덱 
비선형 구조 - 트리 , 그래프 

 

이런 자료구조를 선택할 때는 자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라

여러 가지 종류의 자료구조 중 하나를 선택할 해야 합니다.

 

위에 설명 처럼 자료구조는 보다 효율적인 알고리즘을 사용하게 하는데 알고리즘을 자료구조가 가지는 성능을 알아봐야 합니다.

 

알고리즘 성능

알고리즘의 성능 분석은 크게 시간 복잡도 , 공간 복잡도로 평가합니다.

 

시간 복잡도(Time Complexity) -  알고리즘의 수행시간 분석결과
공간 복잡도(Space Complexity) -  알고리즘의 메모리 사용량 분석결과

 

쉽게 얼마나 오래 걸리고 얼마나 많은 메모리를 사용하느냐 입니다.

시간 복잡도(Time Complexity)
: 알고리즘이 얼마나 빠른지 나타내는데 쉽게 연산 횟수를 세고 거기에 처리 해야 할 데이터의 수에 연산횟수의 T(n)을 구성합니다.


순차 탐색 알고리즘 (Linear Search)

int Search(int arr[], int length, int findNum)
{

    for (int i = 0; i < length; i++)
    {
        if (arr[i] == findNum)
            return i;
    }
 
    return -1;
}
 
void main()
{
    int arr[] = { 1, 8, 3, 4, 2 };
 
    int index;
 
    index = Search(arr, sizeof(arr), 4);
 
    if (index == -1)
        cout << "탐색 실패" << endl;
    else
        cout << "탐색 성공 , 찾은 위치 = " << index << endl;
 
}

위와 같은 알고리즘의 시간 복잡도를 계산해 보자면,

int Search(int arr[], int length, int findNum)
{
    for (int i = 0; i < length; i++) //n + 1
    {
        if (arr[i] == findNum) // n
            return i; // +1
    }
 
    return -1; // +1
}

최악의 경우 찾는 숫자가 없거나 마지막에 있을 경우 모든 데이터를 확인하게 됩니다.

(정렬되지 않은 배열에서 가장 작은 수 또는 가장 큰 수를 탐색할 경우를 생각해봅시다.)

이 알고리즘의 시간 복잡도는 2n + 2 입니다.
데이터의 수가 n 개이므로 , 데이터에 수의 따라서 점차 시간이 길어지게 됩니다.
이 경우를 T(n) = n (O(n))이라고 하는데 이 계산 방식은 나중에 빅-오 표기법을 하면서 다시 해보겠습니다.


이진 탐색 알고리즘 (Binary Search)

순차 탐색 알고리즘 보다 조금 더 빠른 같은 이진 탐색 알고리즘 입니다.
쉽게 데이터의 중앙 위치로부터 값을 비교해서 다시 절반으로 나누어 찾아가는 알고리즘 입니다.

int Search(int arr[], int length, int findNum)
{
    int first = 0;
    int end = length - 1;
    int mid;
 
    while (first <= end)
    {
        mid = (first + end) * 0.5;
 
        if (findNum == arr[mid])
        {
            return mid;
        }
        else
        {
            if (findNum < arr[mid])
                end = mid - 1;
            else
                first = mid + 1;
        }
    }
 
    return -1;
}
 
void main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
 
    int index;
 
    index = Search(arr, sizeof(arr), 4);
 
    if (index == -1)
        cout << "탐색 실패" << endl;
    else
        cout << "탐색 성공 , 찾은 위치  = " << index << endl;
 
}

 

순차 탐색 알고리즘 보다는 입력 자료에 따라서 시간이 크게 증가하지 않습니다.
이진 탐색 알고리즘의 경우 로그 시간 (Logarithmic Time)으로 시간 복잡도를 표시합니다.

 

로그 시간 (Logarithmic Time)
 컴퓨터가 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용한다. (즉, log2n, 때때로는 lg n 이라고 쓰임.) 그러나, 로그의 밑이 변할 때, logan와 logbn는 오로지 상수 승수에 따라서만 달라지며 이것은 빅-오 표기법에서는 버림한다. 그러므로 O(log n)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 된다.

쉽게 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어들게 되었을때 이 로그 시간으로 시간 복잡도를 표시합니다.

처음 데이터의 수가 n개 일 때 반으로 줄여서 그 수가 n/2 , n/4 로 줄어들게 되지만 만약 데이터의 수가 증가하게 되고 찾는 

데이터가 마지막에 있을 때를 생각하자면 비교 연산 횟수를 k 라고 가정하고 마지막에 비교 연산을 1회 진행하므로
T(n) = K +1  이라고 하고 몇 번을 반으로 나누어야 1이 되는 가를 계산한다면,

 

가 됩니다. - 제곱은 

 이므로

위와 같은 식이 성립됩니다.

 

따라서 

입니다.

 

[참고]
- [서적]윤성우의 열혈 자료구조
- 위키 백과 [시간 복잡도]
https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84