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

Q. 알고리즘이란?

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

 

Q. 알고리즘의 평가 기준?

A. 알고리즘이 사용하는 시간 + 알고리즘이 사용하는 공간

 

1. 도입

Q. 알고리즘의 수행시간측정 기준은?

A. 반복문이 지배한다. 즉, 반복문이 수행되는 횟수로 측정가능하다.

 

2. 선형 시간 알고리즘

ex) 다이어트 현황 파악

- 이동평균 계산하기

 

Q. M-이동평균이란?

A. 마지막 M개의 관찰 값의 평균!

 

Q. 선형 시간 알고리즘이란?

A. 입력의 크기에 대비해 걸리는 시간을 그래프로 나타내면 정확히 선형(직선)형태를 가진다.

 

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

ex) 성현 전 사진 찾기

- 이진탐색

 

Q. 선형 이하 시간 알고리즘이란?

A. 입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘

 

이진탐색 알고리즘

오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때, $ A[i-1]<x\leqA[i]$인 i를 반환

($A[-1]=-\infty,A[N]=\infty$RKWJD)

-> i가 주어지고 나면 A[i]값 계산하기, 미리 계산할 필요 없음

 

4. 지수 시간 알고리즘

1) 다항 시간 알고리즘

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

ex) 알러지가 심한 친구들 -> 재귀호출

 

2) 지수 시간 알고리즘 

- N이 하나 증가할 때 마다 걸리는 시간이 배로 증가하는 알고리즘

ex) 소인수 분해의 수행시간

 

5. 시간 복잡도

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

- 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수(더 작게 쪼갤 수 없는 최소 크기의 연산)를 입력의 크기에 대한 함수로 표현한 것

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

 

1) 수행 시간의 종류

- 최선의 수행시간 : 찾으려는 원소가 가장 앞에 있는 경우

- 최악의 수행시간 : 찾으려는 원소가 가장 마지막에 있는 경우

- 평균 수행시간 : 존재하는 모든 입력의 등장 확률이 동일하다고 가정, 기대치 구하기

-> 주로 최악의 수행 시간 혹은 평균 수행시간을 사용

 

2) 점근적 시간 표기 : O표기

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

O(1) : 상수시간 알고리즘

ex) $ N^2M+Nlog(M)+NM^2=O(N^2M+NM^2) $

$ 42=O(1) $

 

3) O 표기법의 의미

- 함수의 상한을 나타낸다.

 

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

주먹구구 법칙

- 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 존재한다.

 

주의해야 할 경우

1) 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우

2) 반복문의 내부가 복잡한 경우

3) 메모리 사용 패턴이 복잡한 경우

4) 언어와 컴파일러의 차이

5) 구형 컴퓨터를 사용하는 경우

 

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

계산 복잡도 클래스 : 같은 성질을 갖는 문제들을 모아놓은 집합

환산 : 한 문제를 다른 문제로 바꿔서 푸는 개념

 

P : 다항 알고리즘이 존재하는 문제들의 집합

NP : 답이 주어졌을 때, 이것이 정답인지를 다항 시간 내에서 확인할 수 있는 문제

P C NP

NP-난해 : 다항시간 안에 푸는 법 발견하지 못한 문제

NP-완비 : NP-난해 문제이면서 NP인 문제