Skip to content

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

Jump to bottom
H0zzae edited this page Nov 17, 2019 · 9 revisions

0. 개관

  • 알고리즘이란?
    주어진 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것
    주관적이거나 모호한 것은 알고리즘이라고 할 수 없음
  • 알고리즘을 평가하는 두 가지의 큰 기준
    시간, 공간

1. 도입

알고리즘의 수행 시간의 측정 기준은 프로그램의 실행 시간일까?

아님.

  1. 사용한 프로그래밍언어, 하드웨어, 운영체제, 컴파일러 등 다양한 요소에 의해 프로그램의 실행 시간은 바뀔수 있음.
  2. 다양한 입력에 대한 실행 시간을 반영하지 못함.

그러면 대체 알고리즘의 수행 시간은 어떤 기준으로 측정해야 할까?

정답은?시간복잡도!!!
  • 알고리즘의 수행 시간을 지배하는 반복문.
    • 한가지 항목이 전체의 대소를 좌지우지 하는것을 지배한다(dominate)라고 표현한다.
    • 반복문은 알고리즘의 수행 시간을 지배한다.

2. 선형 시간 알고리즘

  • 다이어트 현황 파악: 이동 평균 계산하기
    • 이동평균 ? : 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준
  • 선형 시간 알고리즘 ?
    • 입력의 크기에 대비해 걸리는 시간을 그래프로 그려보면 정확이 직선이 되는 알고리즘
    • 선형 시간 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘

3. 선형 이하 시간 알고리즘

  • 선형 이하 시간 알고리즘
    • 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘
    • ex) 이진 탐색 알고리즘: log₂N

4. 지수 시간 알고리즘

  • 다항 시간 알고리즘
    • 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘
    • 다항식 ? 변수 N과 N², 그 외 N의 거듭제곱들의 선형 결합으로 이루어진 식들
    • 다항 시간 알고리즘 간에는 엄청나게 큰 시간 차이가 날 수 있음.
      • 이 알고리즘이 충분히 빠르다고 할 수 없음.
      • ex) N과 N⁴²둘 다 다항시간임.
  • 지수 시간 알고리즘
    • N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘
    • ex) 2ⁿ
    • 가장 큰 수행 시간 중 하나로, 입력의 크기에 따라 다항 시간보다 훨씬 빠르게 증가

5. 시간복잡도

  • 시간복잡도는 가장 널리 사용되는 알고리즘의 수행시간기준
  • 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
  • 기본적인 연산의 수? 더 작게 쪼갤 수 없는 최소 크기의 연산
  • 시간 복잡도가 높다 == 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다.
  • 시간 복잡도가 낮다 != 더 빠르게 동작하는 것은 아니라는 것
  • p. 107 그림 4.3참고
  • 시간 복잡도는 완전한 속도의 기준은 아님
  • cf) 입력의 크기가 매우 작을 경우 시간복잡도는 의미X
  • 입력의 종류에 따른 수행 시간의 변화
    • 입력이 어떤 형태로 있는지도 수행 시간에 영향을 미침
    • 알고리즘의 수행 시간은 크게 3가지로 나눌 수 있음
      1. 최선의 수행 시간
      2. 최악의 수행 시간
      3. 평균적인 경우의 수행 시간
      • 이중에서 최선, 최악 두개를 대게 사용함.
      • 여러 알고리즘에서 이 두 기준이 거의 같기 때문에 따로 구분되지 않고 쓰임
      • ex) ## 0. 개관
  • 알고리즘이란?
    주어진 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것
    주관적이거나 모호한 것은 알고리즘이라고 할 수 없음
  • 알고리즘을 평가하는 두 가지의 큰 기준
    시간, 공간

1. 도입

알고리즘의 수행 시간의 측정 기준은 프로그램의 실행 시간일까?

아님.

  1. 사용한 프로그래밍언어, 하드웨어, 운영체제, 컴파일러 등 다양한 요소에 의해 프로그램의 실행 시간은 바뀔수 있음.
  2. 다양한 입력에 대한 실행 시간을 반영하지 못함.

그러면 대체 알고리즘의 수행 시간은 어떤 기준으로 측정해야 할까?

정답은?시간복잡도!!!
  • 알고리즘의 수행 시간을 지배하는 반복문.
    • 한가지 항목이 전체의 대소를 좌지우지 하는것을 지배한다(dominate)라고 표현한다.
    • 반복문은 알고리즘의 수행 시간을 지배한다.

2. 선형 시간 알고리즘

  • 다이어트 현황 파악: 이동 평균 계산하기
    • 이동평균 ? : 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준
  • 선형 시간 알고리즘 ?
    • 입력의 크기에 대비해 걸리는 시간을 그래프로 그려보면 정확이 직선이 되는 알고리즘
    • 선형 시간 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘

3. 선형 이하 시간 알고리즘

  • 선형 이하 시간 알고리즘
    • 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘
    • ex) 이진 탐색 알고리즘: log₂N

4. 지수 시간 알고리즘

  • 다항 시간 알고리즘
    • 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘
    • 다항식 ? 변수 N과 N², 그 외 N의 거듭제곱들의 선형 결합으로 이루어진 식들
    • 다항 시간 알고리즘 간에는 엄청나게 큰 시간 차이가 날 수 있음.
      • 이 알고리즘이 충분히 빠르다고 할 수 없음.
      • ex) N과 N⁴²둘 다 다항시간임.
  • 지수 시간 알고리즘
    • N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘
    • ex) 2ⁿ
    • 가장 큰 수행 시간 중 하나로, 입력의 크기에 따라 다항 시간보다 훨씬 빠르게 증가

5. 시간복잡도

  • 시간복잡도는 가장 널리 사용되는 알고리즘의 수행시간기준
  • 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
  • 기본적인 연산의 수? 더 작게 쪼갤 수 없는 최소 크기의 연산
  • 시간 복잡도가 높다 == 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다.
  • 시간 복잡도가 낮다 != 더 빠르게 동작하는 것은 아니라는 것
  • p. 107 그림 4.3참고
  • 시간 복잡도는 완전한 속도의 기준은 아님
  • cf) 입력의 크기가 매우 작을 경우 시간복잡도는 의미X

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

  • 입력이 어떤 형태로 있는지도 수행 시간에 영향을 미침
  • 알고리즘의 수행 시간은 크게 3가지로 나눌 수 있음
    1. 최선의 수행 시간
    2. 최악의 수행 시간
    3. 평균적인 경우의 수행 시간
    • 대게 최악의 수행 시간과 수행 시간의 기대치를 대게 사용함.
    • 여러 알고리즘에서 이 두 기준이 거의 같기 때문에 따로 구분되지 않고 쓰임
    • 물론 최악의 수행 시간과 수행 시간의 기대치가 매우 다른 알고리즘도 있음
    • ex) 퀵정렬

점근적 시간 표기 : O 표기

  • O 표기법은 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법.
  • O 표기법의 의미
    • 대략적으로 함수의 상한을 나타낸다
    • 상한? 가장 빨리 증가하는 항
  • O 표기법은 최악의 수행 시간과 관련없음
값 O(f(x))
2ⁿM O(2ⁿM)
N²M/64 + 64NM O(N²M/64)
N²M + NlgM + NM² O(N²M + NM²)
42 O(1)

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

  • 알고리즘의 시간 복잡도를 항상 반복문의 개수를 세는 것으로만 결정하지 않음
  • 더 정확한 시간 복잡도를 계산 가능
  • 분할 상환 분석을 이용하면 일반적으로는 시간이 오래걸려 실행하지 못할 것이라고 여겼던 작업이 시간안에 돌아가는 것을 이해할 수 있게됨.
  • 하나의 수행시간을 보는 것이 아니라 전체 수행시간을 고려하여 그 평균을 보고 복잡도 등을 계산하는 것을 말함

6. 수행 시간 어림짐작하기

주먹구구 법칙

  • 프로그램을 작성하기 전에 수행 시간을 어림짐작 할 수 있어야 함
  • but 프로그램의 동작 속도에 영향을 끼치는 요소가 엄청나게 많음
  • 그러나 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적인 짐작 가능
    • 시간 복잡도는 프로그램의 수행 시간에 가잔 큰 영향을 미치는 요소이기 때문
  • 그래서 주먹구구 법칙이 뭔데?
    • 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다.

주먹구구 법칙은 주먹구구일 뿐이다.

  • 기준보다 느리지만 시간안에 수행되거나 기준보다 빠르지만 시간안에 수행되지 않는 프로그램들도 있음
  • 시간 복잡도 외에도 다른 요소들을 참조해 시간 안에 수행될지를 판단해야 함
    • 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
    • 반복문의 내부가 복잡한 경우
    • 메모리 사용 패턴이 복잡한 경우
    • 언어와 컴파일러의 차이
    • 구형 컴퓨터를 사용하는 경우

7. 계산복잡도 클래스 : P, NP, NP-완비

  • 시간 복잡도는 알고리즘의 특성이지 문제의 특성이 아님.

문제의 특성 공부하기

  • 계산 복잡도 이론은 각 문제의 특성을 공부하는 학문
  • 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타냄
  • 빠른 알고리즘의 기준은 다항 시간 알고리즘.
  • 계산 복잡도 클래스
    • 같은 성질을 갖는 문제들을 모아놓은 집합
    • P문제
      • 다항시간 알고리즘이 존재하는 문제들의 집합
    • NP문제
      • 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제
      • 모든 P문제는 NP문제에 포함된다

난이도의 함정

  • 계산 복잡도에서의 어려운 문제의 정의
    • 정말 어려운 문제를 잘 골라서 이것을 어려운 문제의 기준으로 삼는다
    • 그리고 앞으로는 기준 문제만큼 어렵거나 그보다 어려운 문제들, '기준 이상으로 어려운 문제들'만을 어렵다고 부른다
  • 그렇지만 이 정의는 난이도 판정이 쉽지 않다는 난관에 부딪힘
  • 그래서 두 문제의 난이도를 비교하기 위해 환산(reduction) 이라는 기법을 이용함
    • 환산? 한 문제를 다른 문제로 바꿔서 푸는 기법

NP문제, NP 난해 문제

  • SAT문제는 어려운 문제의 기준임
    • SAT문제? N개의 boolean값 변수로 구성된 논리식을 참으로 만드는 변수값들의 조합을 찾는 문제
  • SAT문제는 모든 NP문제 이상으로 어렵다.
  • SAT를 다항 시간에 풀 수 있으면 NP문제들을 전부 다항 시간에 풀 수 있다는 얘기
  • NP-난해(NP-Hard) 문제
    • 모든 NP문제를 다항식 시간내에 환원(reduction)할 수 있는 문제
    • 아무도 NP-난해 문제를 다항 시간에 푸는 방법을 발견못함
  • NP-완비(NP-Complete) 문제
    • NP-난해 문제이면서 NP문제인 문제들 ex) 부분 집합 합 문제

P=NP?

  1. NP-난해 문제 중 하나를 다항 시간에 풀 수 있다면, 이 알고리즘을 이용해 NP에 속한 모든 문제를 다항 시간에 풀 수 있다 - NP에 속한 모든 문제를 다항 시간에 해결할 수 있으므로 P=NP임을 알 수 있다
  2. NP문제 중 하나를 골라 P에 포함되어 있지 않음(다항 시간에 푸는 방법이 없음)을 증명하면 P≠NP임
  • 아직까지 미해결인 문제
    • 아무도 둘 중 하나에 성공한 사람이 없음.

#. 8. 더 읽을거리

  • 마스터정리(Master Theorem)
    • 재귀적인 알고리즘의 시간 복잡도를 계산하는 쉬운 방법
    • 어떤 함수의 수행 시간이 특정 형태의 함수로 표현될 때 이 함수의 O 표기법을 쉽게 계산할 수 있도록 도와줌
    • 복잡한 분할 정복 알고리즘이 시간 안에 동작할지 의문일 때 종종 도움됨.
Clone this wiki locally