Data_Structure Ch.1

Chapter 1. Basic Concepts

Intro

프로그램의 개발 과정은 다음과 같다. 문제를 정의하고, 이를 부분으로 나눈 다음에 적절한 자료구조와 알고리즘을 선택한다. 이를 코드로 표현하며 코드가 타당한지 테스트하고 오류를 제거한다.

What is Algorithms?

알고리즘은 유한한 작업의 집합이며, 특정한 일을 수행할 수 있다. 알고리즘은 무조건 I/O, 명확성(Definiteness), 유한성(Finiteness), 효율성(Effectiveness) 을 만족시켜야 한다. 대표적인 예로 Selection Sort, Binary Search가 있다.

Recursive Algorithms

재귀함수는 일반 코드에 비해 좀 더 직관적으로 이해하기 쉽다. 대표적인 예로 Permutation을 구하는 함수가 있다.

void permutation(int *arr, int cur, int n){
    if(cur == n){
        for(int i = 0; i < cur; i++){
            cout << arr[i] << "\n";
        }
        return;
    }
    for(int i = cur; i <= n; i++){
        swap(arr[cur], arr[i]);
        permutation(arr, cur + 1, n);
        swap(arr[cur], arr[i]);
    }
}

Data Abstraction

C에는 다양한 자료형이 있다. 이를 Struct로 그룹화 해서 새로운 자료형을 만들 수도 있다. 포인터 자료형 또한 존재하는데, 이 자료형은 자신과 동일한 자료형을 지닌 일반 변수의 주소를 저장한다. Data Type란 객채들의 집합이며 해당 객채들의 연산 집합을 의미한다. Abstract Data Type(ADT)이란 data type를 묶어 객채를 만들고, 그 객체에 해당하는 연산들을 만든 것을 의미한다. 각 자료형에서 하는 연산을 크게 1. Creator/Constructor(생성자), 2. Transformers(변환자), 3. Observers/Reporters(관찰자) 로 분류한다.

Performance Anlysis

프로그램을 평가할 때에는 다음과 같은 기준으로 판단한다.

1. 프로그램이 요구 사항을 충족하는가?
2. 프로그램이 올바르게 작동하는가?
3. 프로그램이 잘 문서화 되어있고 코드가 읽기 편한가?
4. 프로그램이 효과적으로 함수를 사용하는가?
5. 프로그램이 저장공간을 효율적으로 사용하는가?
6. 프로그램의 실행 시간이 해당 작업에 적합한가?

Space Complexity

공간복잡도(Space Complexity)는 실행 완료하는데에 있어 필요한 메모리의 양을 의미하고, 시간복잡도(Time Complexity)는 프로그램의 실행 완료까지의 걸리는 시간의 양을 의미한다. 공간복잡도를 파악할 때에는 parameters가 passed by value, or reference일지, 재귀적으로 작동하는지를 보고 계산하면 된다.

Time Complexity

시간 복잡도(Time Complexity)는 컴파일 시간이 아닌 실행 시간만 카운팅한다. 또한, 카운팅할때는 절대적인 시간이 아닌 반복 횟수 및 계산 횟수, 다시 말해 Program Step만 센다. 이로 인해 컴퓨터에 성능과 관계없는 절대적인 성능 추정치를 알 수 있다. 다만, 세세한 사항을 하나하나 더하고 고려하기에는 너무 복잡하다. 그래서 우리는 최소, 최대, 중간값을 고려한다.

Big O Notation

시간복잡도의 Upper Bound를 의미한다.

\[f(n) = O(g(n)) \Leftrightarrow \exists c > 0 \text{ and } n_0 \text{ s.t } f(n) \leq cg(n) \,\,\forall n\geq n_0\]

Big Omega Notation

시간복잡도의 Lower Bound를 의미한다.

\[f(n) = \Omega (g(n)) \Leftrightarrow \exists c > 0 \text{ and } n_0 \text{ s.t } f(n) \geq cg(n) \,\, \forall n \geq n_0\]

Big Theta Notation

시간복잡도의 중앙값을 의미한다.

\[f(n) = \theta (g(n)) \Leftrightarrow \exists c_1, c_2 \text{ and } n_0 \text{ s.t } c_1g(n) \leq f(n) \leq c_2g(n) \,\,\forall n \geq n_0\]

대소관계 비교

통상적인 대소관계는 다음과 같다.

\[O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\]

Algorithm test

C에서는 time.h헤더를 이용하여 대략적인 테스트가 가능하다.
테스트데이터를 만드는 것은 쉽지 않다. 적당히 큰 랜덤의 데이터를 만들어야하는데, 이는 알고리즘 분석에서 매우 중요한 역할을 맡는다.