• 알고리즘을 평가하는 요소
    • 시간: 얼마나 빠르게
    • 공간: 더 적은 용량의 메모리를 사용
    • 시간과 공간은 대부분 상충, Ex) 동적 계획법

4. 알고리즘의 시간 복잡도 분석

4.1 개요

  • 반복문이 알고리즘 수행 시간을 지배한다(dominate), 한 가지 항목이 전체의 대소를 좌지우지 한다 === dominate
    • 반복문이 수행되는 횟수를 입력의 크기에 대한 함수로 표현

4.2 선형 시간 알고리즘

  • 수행 시간이 N에 정비례
  • 주어진 입력을 최소한 한 번씩 쳐다보면 선형 시간 (linear time) 이 걸린다.

4.3 선형 이하 시간 알고리즘

  • Ex) 이분 탐색, 이진 탐색: log2 N (=== lgN)
  • 이진 탐색 과정에서 얼마가 걸리건 간에 전체 는 선형 시간이 아니냐? 정렬도 필요하니까
    • 탐색 배열을 A[] 모두 미리 계산해서 가질 필요 없이 A[i]가 필요할 때만, 계산하면 된다.
    • 정렬과 탐색은 별개 이다. 한번 정렬 한 데이터는 2번 이상 계속 쓰일 수 있다.

4.4.1 다항 시간 알고리즘

  • 다항식: N의 거듭제곱들의 선형 결합으로 이루어진 식들
  • 다항식으로 표현할 수 있는 알고리즘이 다항 시간 알고리즘이다.

4.4.2 지수 시간 알고리즘

  • N이 하나씩 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘 (2^N, 3^N …)
  • 입력의 크기에 따라 다항 시간과는 비교도 안 되게 빠르게 증가

4.5 시간 복잡도

  • 시간 복잡도(time complexity): 가장 널리 사용되는 알고리즘의 수행 시간의 기준

    • 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것

    • 반복문 내부의 있는 연산들은 더 쪼갤 수 없기 때문에, 이것이 시간 복잡도의 대략적인 기준이 된다.

  • 시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미

  • 시간 복잡도는 절대적 빠르기의 기준이 아니다. 입력의 크기에 따라 다름 (2^5 < 10^2)

  • 최선의 수행 시간, 최악의 수행 시간, 평균적인 수행 시간

    • 여러 알고리즘에서 평균과 최악의 수행 시간이 비슷함으로 두 개를 구분 하지 않고 쓰인다.

4.5.1 점근적 시간 표기: O 표기

  • 시간 복잡도는 계산하기 너무 힘들다는 문제가 있다.

    • 명령어 수가 애매 모호하고, 세기 힘들다
    • 따라서, 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 된다.

  • 여기에서 한 발짝 더 나아가서 사람들이 이것을 더욱 간단하게 표현한 O 표기법(Big-O Notation) 이라는 것을 사용해 알고리즘의 수행 시간을 표기한다.

  • O 표기법은 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다.

  • O 표기법을 쓸 때, 시간 복잡도는 반복문에 의해서 결정되기 때문에, 반복문들이 몇 번이나 실행되는지만 보면 되기에 간단하다.

  • O 표기법은 함수의 상한을 나타내는데 의미가 있다.

    • 상한을 나타내기에 알고리즘의 최악의 수행 시간을 나타낸다고, 착각 할 수도 있다.
    • 하지만, O 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련이 있는 것은 아니다.
      • 퀵 정렬의 최악의 시간 복잡도는 O(N^2) 이고, 평균 시간 복잡도는 O(NlgN) 이다.

4.5.2 시간 복잡도의 분할 상환 분석

  • 시간 복잡도를 항상 반복문의 개수로 결정하지는 않는다.
  • 더 정확한 시간 복잡도는 분할 상환 분석 을 사용한다.
  • N개의 작은 작업들을 순서대로 할때, 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 적용할 수 있다.
    • 시간이 오래 걸려 실행하지 못할 것이라고 여겼던 작업이 시간 안에 돌아가는 것을 이해할 수 있게 된다.
    • Ex) N명이 N잔의 막걸리가 담긴 사발을 먹을 때: 각 신입생 마다 평균적으로 한 잔의 막걸리를 마셨다고 할 수 있다.

4.6 수행 시간 어림짐작하기

  • 입력의 크기(N) 을 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8, 100,000,000) 넘어가면 시간 초과 할 가능성이 있다.
    • 시간 제한이 5초면 500,000,000, 시간 제한이 10초면, 1,000,000,000 // 1초: 10^8은 보수적으로 정한 것이다.
  • 어림짐작이기 때문에 이보다 작아도 통과 될 수도 있고, 반대일 수 도 있다.

5. 알고리즘의 정당성 증명

5.1. 개요

  • 단위 테스트는 알고리즘에 문제가 있음을 증명할 수 있어도, 문제가 없음을 증명할 수 없다.
  • 따라서, 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원 되어야 한다.
  • 알고리즘의 증명이 알고리즘을 유도하는데 결정적인 통찰을 담고 있기에 중요하다.

5.2 수학적 귀납법과 반복문 불변식

5.2.1 수학적 귀납법

  1. 단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다.
  2. 첫 단계 증명
  3. 귀납 증명: 1 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립합을 보인다.

5.2.2 반복문 불변식

  • 반복문 불변식: 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건
    • 반복문이 마지막 정답을 계산하기 위해서는 항상 이 식이 변하지 않고(불변식) 성립해야 한다.
  1. 반복문 진입시에 불변식이 성립함을 보인다
  2. 반복문 내용이 시작할 때 불변식이 성립했다면, 내용이 끝날 때도 불변식이 항상 성립함을 보인다.
  3. 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.
1
2
3
4
5
6

// * 불변식은 여기에서 성립해야 한다.
while (어떤 조건) {
    // 반복문 내용의 시작
    // 반복문 내용의 끝
    // ** 불변식은 여기에서도 성립해야 한다.
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 이진 탐색, 파이썬 코드
def binsearch(A: list, x: Int) {
    n = len(A)
    lo, hi = -1, n
    
    # 반복문 불변식 1: lo < hi
    # 반복문 불변식 2: A[lo] < x <= A[hi]
    while(lo + 1 < hi):
        mid = (lo + hi) // 2
        if A[mid] < x:
    		lo = mid
   		else:
    		hi = mid
    # 불변식은 여기서도 성립해야 한다.    
    
    return hi
}

  • lo + 1 = hi: while 문이 종료했으니, lo +1 >= hi 인데, 불변식에 의하면 lo <hi 이니 lo + 1 = hi 일 수 밖에 없다. (ex.lo:3, hi:4)

  • A[lo] < x <= A[hi]: 애초에 불변식이 성립한다고 가정했으니 이것은 당연히 성립한다.

  • 우리가 원하는 결과값 i는 A[i-1] < x <= A[i] 인 i 이므로, 이때 우리가 원하는 답은 hi라는 사실을 알 수 있다.

  • 이때, 반복문의 정당성은 귀납법과 다를 것이 없다.

  • 이런 과정을 거쳐 while문이 종료 될때, 우리가 원하는 값이 A[hi] 에 저장되어 있음을 알 수 있다.

5.3 귀류법

  • 귀류법: 우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법
    • 보통 어떤 선택이 항상 최선임을 증명하고자 할 때 많이 이용된다.
    • 우리가 선택한 답보다 좋은 답이 있다고 가정한 후, 사실 그럴 일이 있을 수 없을 보이면 우리가 최선의 답을 선택했음을 보일 수 있다.

5.4 다른 기술들

5.4.1 비둘기집의 원리

  • 10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어 간 비둘기집이 반드시 무조건 하나는 있게 마련이다.

5.4.2 구성적 증명

  • 답이 존재한다는 사실을 논증하는 것이 지금까지 다룬 방식이라면,
  • 구성적 증명은 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시하는 증명이다.
    • Ex. 하늘을 나는 교통 수단을 만들 수 있다는 주장을 증명하려한다.
    • 비구성적 증명: 양력의 법칙, 지구의 공기 밀도 등등을 따져서 증명한다.
    • 구성적 증명: 비행기를 만들어서 보여주거나, 비행기 만드는 설명서를 보여준다.
  • ‘답이 존재하는가’ 에 대한 답으로 ‘이렇게 만들면 된다’ 라고 하는 것이다.
  • 구성적 증명의 내용은 사실상 알고리즘 그 자체인 경우가 많다.

Reference