(TIL) 20210607

📕Facts(한 것)

---

• 알고리즘 복습
• 운동하기
• 프로그래머스 문제 풀기
• 수업듣기

 

📕Findings(배운 것)

---

시간복잡도를 계산하는 여러가지 방법과, 병합정렬에 관해서 공부했다.

알고리즘의 performance를 측정하는 척도는 시간인데,

이 시간을 측정하는 방법이 여러가지가 있다.

대표적으로 수학적으로 계산하며 단순 작업의 양을 나타내는 방법인 Mathematical model과

그래프로 표현하여 performance salce을 나타내는 Asymptotic analysis 방식이 있다.

 

Matehmatical model은 sum of "cost" * "freuqency" 이다. 

cost 는 variable declaration ,assignment statement, less than compare,

equal to compare, array access, increment 등의 항목으로 측정된다.

그 후 나타내어진 sum은 최고차항으로만 Comlexity를 표기한다.

 

ex : 1/6n^3 + 20n + 16 => 1/6n^3

 

 

Asymptotic analysis 방식에는 크게 세가지 방식이 있다.

Big-Oh, Big-Omega, Big-Theta.

 

가장 대표적인 Big-Oh 표기법은 upperbound로 그 average값을 나타내며,

최고차항 이하의 수를 절삭하고, 최고차항의 계수를 제외하고 표기한다.

 

ex) 6nlogn + 6 = O(nlogn)

 

Big-Omega 표기법은 LowerBound로 빅오 표기법과 반대되는 표기법이다.

가장 minimum 한 average값을 나타낸다.

 

BIg-Theta 표기법은 알고리즘의 실제 성능을 나타낼때 주로 쓰이며, 실제 성능에 가장 근접한 성능을 표기한다.

 

 

흔히 대략적인 성능을 알기 위해서 BIg-Oh 표기법을 사용하는데, 대략적인 모델을 알기 위해서는 Tilde-notation을 사용한다.

 

---

병합정렬은 빠르면서 stable한 정렬 알고리즘이다.

그렇기에 high-level language에서 기본 함수로 제공되는 많은 sort 알고리즘은 대부분 merge-sort에 기반하거나

merge-sort에 가까운 성능을 내준다. (대표적으로 C++ 의 stable sort)

 

아래는 C로 작성된 병합정렬 코드이다.

 

void merge(int a[], int low, int mid, int high) {
    for(int k = low; k <= high; k++) {
        array[k] = a[k];
    }
    
    int i = low;
    int j = mid + 1;
    
    for(int k = low; k <= high; k++) {
        if (i > mid) {
            a[k] = array[j++];
        } else if (j > high) {
            a[k] = array[i++];
        } else if (array[j] < array[i]) {
            a[k] = array[j++];
        } else {
            a[k] = array[i++];
        }
    }
}

 

 

병합정렬은 in-place 정렬 알고리즘이 아니기 때문에 배열을 필요로한다.

하지만 그 속도는 O(nlogn)을 보장하기 때문에, 메모리에서 약간의 손해를 보더라도

실행시간에 큰 이점을 가져갈 수 있다.

 

 

📕Feeling(느낀 점)

---

학교 실시간 수업이 있는 날은 어쩔 수 없이 시간을 많이 빼앗긴다.

그럼에도 얻어갈 수 있는 것들이 많아서 아깝지 않다.

 

 

📕Affirmation(자기 선언)

---

• 日日新又日新
• 순간에 최선을

 

📕여담

---

시험 6과목 중 2과목이 과제 제출이기 때문에 약간의 부담은 덜은 것 같았지만

오히려 과제가 발목을 잡는 일이 발생했다.

 

3대 400프로젝트를 시작하려고 보니 의도치 않게 다이어트 중임을 인지했다.

시험끝나고 진행해야겠다.