[Algorithm] 알고리즘 시간 복잡도 분석

참고글 : [Algorithm] 프로그램 수행 시간 짐작하기

#. 알고리즘

  ㅇ 알고리즘

    - 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법

    - 주관적이거나 모호한 것은 알고리즘이라고 할 수 없음

  ㅇ 알고리즘이 사용하는 시간과 공간

    - 시간 : 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 이야기

    - 공간 : 알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 이야기

  ㅇ 알고리즘 시간 분석도 분석

    - 프로그램의 실행 시간을 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합

    - 이유 1. 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있음

    - 이유 2. 프로그램의 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못함, 입력의 크기나 특성에 따라 수행 시간이 달라짐

  ㅇ 반복문

    - 한 가지 항목이 전체의 대소를 좌지우지 하는 것을 '지배한다' 라고 표현

    - 알고리즘의 수행 시간을 지배하는 것은 ? 반복문

    - 대개 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정

    - ex) N 번 반복하는 반복문이 2개 있다면, 이 알고리즘의 수행 시간은 N^2

  ㅇ 이동 평균 (Moving Average)

    - 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준

    - 이동 평균의 성능을 높이기 위해서는 중복된 계산을 없애는 방법이 있음

    - ex) 주식의 가격, GDP, 몸무게 등

  ㅇ 선형 시간(Linear time) 알고리즘

    - 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 그려지는 알고리즘

    - 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘이라 할 수 있음

  ㅇ 선형 이하 시간(Sublinear time) 알고리즘 = 이진 탐색(binary search) 알고리즘

    - 입력의 크기가 커지는 것에 대비해서 수행 시간이 느리게 증가하는 알고리즘 

    - 입력 N이 있을 경우 N을 계속 절반으로 나눠서 1이하가 될 때까지 몇 번이나 나눠야 하는 경우 나타내는 함수 -> 로그(Log)

    - 매 회 절반씩 나눌 경우 밑이 2인 log_2를 사용

    - 이 알고리즘의 복잡도는 log_N

  ㅇ 다항 시간 알고리즘

    - 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들

    - 입력 N과, N^2, N의 거듭제곱들의 선형 결합으로 이루어진 식들을 다항식이라고 부름

    

  ㅇ 지수 시간 알고리즘

    - 여러 개의 답이 있고 그 중 가장 좋은 답을 찾는 문제들을 풀 때 가장 간단한 방법은 모든 답을 일일이 고려해보는 것

       ex) N 가지의 음식 중 만든다, 안 만든다의 두 선택지가 있을 때 -> 만들수 있는 답은 2^N 가지

    - 2^N과 같은 지수 함수는 알고리즘의 전체 수행 시간에 엄청난 영향을 미침

    - N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간(exponential time)에 동작

    - 지수 시간은 가장 큰 수행 시간 중 하나로, 입력 크기에 따라 다항 시간과는 비교도 안 되게 빠르기 증가

#. 알고리즘 시간 복잡도

  ㅇ 시간 복잡도

    - 가장 널리 사용되는 알고리즘의 수행 시간 기준

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

    - 기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산

  ㅇ 시간 복잡도 특징

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

    - 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아님

    - 입력의 크기가 충분히 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있음 (아래 그림의 x축이 0~70 구간)

    - 시간 복잡도가 낮은 알고리즘은 입력이 커지면 커질수록 더 효율적 (아래 그림의 x축이 70~200 구간)

    - ex)  

     

    - 시간 복잡도는 완전한 속도의 기준은 아님

    - 문제에서 해결할 입력의 크기가 매우 작을 경우 시간 복잡도는 큰 의미를 갖지 못할 수 있음

  ㅇ 입력의 종류에 따른 수행 시간 변화

    - 입력의 크기가 수행 시간을 결정하는 유일한 척도는 아님

    - 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향

    - ex) 배열에서 주어진 숫자를 찾아 그 위치를 반환하는 코드가 있다면, 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 최선/최악의 경우, 그리고 평균적인 경우에 대한 수행 시간을 각각 따로 계산해야 함

      ㄴ 최선의 수행 시간 : 찾으려는 원소가 배열의 맨 앞에 위치, 반복문의 수행 횟수는 1 

      ㄴ 최악의 수행 시간 : 배열에 찾으려는 원소가 없을 경우, 반복문의 수행 횟수는 N

      ㄴ 평균적인 경우의 수행 시간 : 주어진 배열이 항상 찾는 원소를 포함한다는 가정, 평균 수행 횟수는 N/2

    - 대개 최악의 수행 시간 혹은 수행 시간의 기대치를 사용

#. Big-O 표기

  ㅇ 시간 복잡도

    - 알고리즘 수행 시간을 표기하는 방법

    - 알고리즘이 실행될 때 필요한 명령어의 수라는 것이 모호하여, 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려

    - 이것을 더욱 간단히 표현하기 위한 방법이 Big-O 표기법

  ㅇ Big-O 표기법

    - 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법

    - ex) (2/3)N^2 - NlogN/2 + 17N - 8 의 Big-O 표기법은 N^2 => O(N^2)

      ex) (3^N)M = O((3^N)M)

      ex) (1/32)N^2M + (32)NM = O(N^2M)

      ex) N^2M + NlogM + NM^2 = O(N^2M+NM^2)

      ex) 32 = O(1)  :  상수 시간(constant-time) 알고리즘

    - 최고차항을 제외한 모든 것을 들어내기 떄문에 Big-O 표기법은 계산하기 간편

    - 알고리즘의 시간 복잡도는 반복문에 의해 결정되므로 반복문들이 몇 번이나 실행되는지만 보면 됨

  ㅇ 예제

for(int i=0; i<N; i++) {
    ...
    for(int j=0; j<N; j++) {
    ...
    }
}

--

--

참고 : 알고리즘 문제 해결 전략