[Algorithm Week_2] 시간복잡도 & 빅-오 표기법

시간복잡도 (Time Complexity)

- Algorithm의 "수행시간"을 이론적으로 분석

• Algorithm은 추상적인 존재
• 이 추상적인 Algorithm을 코드를 통해서 구체화를 한다

- 시간복잡도는 N에 관한 함수로 표현한다

• N : 입력으로 주어지는 Data의 크기

- 시간복잡도의 계산방법은 "해당 코드의 기본연산의 개수"를 계산한다

• 기본연산 : 덧셈 / 뺄셈 / 곱셈 / 나눗셈 / 대입 / ...

- 시간복잡도에는 최선/평균/최악으로 나누어지면 여기서 가장 눈여겨봐야하는 것은 "최악 시간복잡도"이다

• Why? 항상 시간복잡도는 "upper bound"를 고려해야 하기 때문이다

 

 

Example) Selection Sort

static void selection_A(int [] list, int n){
    /*
    - 자신의 값(index)과 그 이후의 값들을 비교해서 작은 값이 존재하면 exchange
     */

    for(int i = 0; i < n - 1; i++){
        int index = i; // 이 index는 결국 index(i) 이후의 값들 중 최솟값의 index가 된다
        for(int j = i + 1; j < n; j++){
            if(list[j] < list[index]){
                index = j;
            }
        }
        // 최솟값의 index를 찾아냈으면 index(i)의 값과 exchange
        int tmp = list[index];
        list[index] = list[i];
        list[i] = tmp;
    }
}

>> 우리가 시간복잡도를 계산할 때는 제일 안쪽에서부터 계산해야 한다

 

1) 제일 안쪽 for문 (int j)

for(int j = i + 1; j < n; j++){
    if(list[j] < list[index]){
        index = j;
    }
}

- 일단 for문의 구조를 살펴보면

• 처음 for문 시작 시 "int j = i + 1;" → 1개 (+)
• for문 루프를 돌 동안 "j < n & j++" → 2개 (<, ++)

- if문을 살펴보면

• 조건을 만족한다면 "list[j] < list[index] & index = j" → 4개 ([], <, [], =)
• 조건을 만족하지 않으면 "list[j] < list[index]" → 3개 ([], <, [])

- 여기서 []라는 것은 "indexing operator"로써 메모리 액세스(배열에 접근)하는 연산이다

 

>> 제일 안쪽 for문에서의 연산개수(worst case) = 6번

>> 루프를 n - (i + 1) - 1 = n-i번 돈다

∴ 제일 안쪽 for문의 worst-case : 6(n-i)

 

2) 바깥쪽 for문 (int i)

for(int i = 0; i < n - 1; i++){
    int index = i; // 이 index는 결국 index(i) 이후의 값들 중 최솟값의 index가 된다
    for(int j = i + 1; j < n; j++){
        if(list[j] < list[index]){
            index = j;
        }
    }
    // 최솟값의 index를 찾아냈으면 index(i)의 값과 exchange
    int tmp = list[index];
    list[index] = list[i];
    list[i] = tmp;
}

- 일단 for문의 구조 살펴보기

• for문 "i < n - 1 & i++" → 3개 (<, -, ++)
  • 초기화 (i = 0)은 기본연산에 포함시키지 않는다 

- Swap 부분

• int tmp = list[index] → 1개 ([])
• list[index] = list[i] → 3개 ([], =, [])
• list[i] = tmp → 2개 ([], =) 

>> 제일 바깥쪽 연산 개수 = 3 + 6(n-i) + 1 + 3 + 2 + 1 = 6(n-i) + 10

• 이 "+ 1"은 처음 for문을 시작할 때 "int i = 0" 부분이다

>> 바깥쪽 루프 횟수 : (n-1) - 0 - 1 = n-2번

 

∴ Selection Sort의 시간복잡도

 

---

빅-오 표기법? (etc 빅-오메가, 빅-세타)

- 이 표기법 자체가 "시간복잡도"를 나타내는 건 아니다

- 이 표기법은 "두 함수간의 관계"를 나타내는 표기법이다

>> 여기서 "두 함수간의 관계" = "두 함수간의 증가 속도를 비교" 

 

1. 빅-오 (Big-Oh)

"f의 증가속도가 g보다 빠르지 않다" :: V(f) ≤ V(g) 

- 이 극한값이 "어떤 양수에 수렴"하거나 "무한대로 발산"할 경우

"Worst Case"

 

2. 빅-오메가 (Big-Omega)

"f의 증가속도가 g보다 느리지 않다" :: V(f) ≥ V(g) 

- 이 극한값이 "어떤 양수에 수렴"하거나 "무한대로 발산"할 경우

"Best Case"

 

3. 빅-세타 (Big-Theta)

"f의 증가속도가 g와 동등하다" :: V(f) ≒ V(g) 

 

※ 빅-세타의 전제조건 : 빅-오 & 빅-오메가 둘다 만족할 경우

- 빅-세타는 극한값이 "0이 아닌 양수에 수렴"할 경우

"Average Case"

 

Example 1)

"f(n) = 3n² + 3n - 16"

빅-오 (1 ~ 4)

1. X : 빅오는 g(n)의 증가속도가 더 빨라야 하는데 함수를 보면 f(n)의 증가속도가 더 빠르다 :: -∞로 발산

2. O : 1/3로 수렴

3. O : ∞로 발산

4. O : ∞로 발산

 

빅-오메가 (5 ~ 8)

5. O : 빅-오메가는 f(n)의 증가속도가 더 빨라야 하는데 함수를 보면 정확하다 :: ∞로 발산

6. O : 3에 수렴

7. X : f(n)의 증가속도가 더 느리다 :: -∞로 발산

8. X : f(n)의 증가속도가 더 느리다 :: -∞로 발산

 

빅-세타 (9 ~ 12)

9. X : f(n) = O(n)이 아니기 때문에 자동적으로 빅-세타를 만족하지 않는다

10. O : 빅-오, 빅-오메가 둘다 만족

11. X : 빅-오메가 만족 X

12. X : 빅-오메가 만족 X

 

 

Example 2)

"f(n) = 3n² + 3n - 16"

빅-오 (1, 2)

1. O : 4에 수렴

2. O : ∞로 발산

 

빅-오메가 (3, 4)

3. O : ∞로 발산

4. O : 1/5로 수렴

 

빅-세타 (5, 6)

5. 빅-오 = 0.2/3에 수렴, 빅-오메가 = 3/0.2에 수렴 :: O

6. 빅-오 = 1/3에 수렴, 빅-오메가 = 3에 수렴 :: O

 

 

---

증가속도에 따른 함수의 서열

>> 각 함수별 시간이 1초인 데이터의 크기 N

• O(N) : 1억
• O(N²) : 1만
• O(N³) : 500
• O(2ⁿ) : 20
• O(n!) : 10