알고리즘 분석

시간 복잡도

 - 알고리즘이 시간적으로 얼마나 효율적인지를 나타내어 주는 지표

 - 데이터 양에 따른 처리 시간 증가가 완만할 수록 알고리즘 효율이 좋음

 

1. 알고리즘

- 알고리즘이란?

 * 추상적, 개략적으로 기술한 조리법

 * 알고리즘을 구체적으로 표현한 것이 프로그램

- 사세성

 * 기본 동작을 언급하되 너무 추상적이거나 구체적이어서는 안됨

- 정확성

 * 허용된 입력에 대해서 제대로 동작해야 함

 * '정확히 우리가 기대하는 것'을 수행해야 함

 

2. 프로그램 오류

- 문법적 오류

 * 명령문 끝에 세미콜론

 * 프로그래머와 컴퓨터 간에 정확한 의사소통

 * 모호성(Ambiguity)을 배제하기 위한 약속

- 의미 상의 오류

 * 프로그래머와 컴파일러 사이의 오해

 * 연산자의 오사용 등

- 논리적인 오류

 * 문법은 맞으나 생각이나 아이디어 자체의 오류

 * 가장 치명적인 오류

 

ex) 문장 중 해당 단어의 개수 찾기

→ 문장의 끝인 마침표까지 읽고

→ 띄어쓰기 별로 나눠서

→ 소득이라는 단어를 찾음

 

3. 알고리즘의 정확성

- 샘플 테스트

 * 부정확성을 증명(오류가 있음을 증명)

 * 정확성을 증명할 수 없음(오류가 없음을 증명할 수는 없음)

 * 정확성 = 가능한 모든 입력에 대해 프로그램이 제대로 작동

- 부정확한 알고리즘의 결과

 * 종료, 무한 루프, 잘못된 결과 출력

 

알고리즘의 분석

1. 분석

- 알고리즘의 효율

효율성 → 복잡도(Complexity)

* 복잡도가 높을수록 효율성은 저하된다.

 

시간적 복잡도 분석

 * 하드웨어 환경에 따라 처리시간이 달라진다.

 1) 부동소수 처리 프로세서 존재 유무, 나눗셈 가속기능 유무

 2) 입출력 장비의 성능, 공유 여부

 * 소프트웨어 환경에 따라 처리시간이 달라진다.

 1) 프로그램 언어의 종류

 2) 운영체제, 컴파일러의 종류

# 이러한 환경적 차이로 인해 객관적 분석이 어렵다.

 

2. 알고리즘의 효율 분석 예

- 점근적 복잡도

 * 실행환경과 무관하게 개략적으로 분석

 * 입력 데이터의 수 = 데이터 크기(Size) = N

 * 실행에 걸리는 시간은 N의 함수(f(N))로 표시

 * 단, N이 무한대로 갈 때의 효율을 표시함으로써 환경적 변수에 의한 영향이 무시됨

 

- 복잡도

 * 할당 한번 시간을 a, 비교 한번 시간을 b, 출력 한번 시간을 c라고 가정

 * 정확한 총 실행 시간은 a(N+1) + bN + cN = (a+b+c)N + a

 * 단순히 "실행 시간이 N에 비례"하는 알고리즘

 

- 입력 크기에 따른 함수 값의 비교

 * logN < N < NlogN < N² < N³ ... < 2ⁿ

 

- 미시에서 거시로의 이동

- 최악의 경우 효율

ex) 데이터 N 개 짜리 정렬되지 않은 배열에서 어떤 레코드를 찾기

 * 최선의 경우: 운이 좋으면 첫 번째 데이터가 찾고자 하는 것. 1번 비교

 * 최악의 경우: 배열 끝에 찾고자 하는 것, N번 비교

 * 평균적 경우: 대략 배열의 반 정도 만에 찾음. N/2번 비교

 

빅 오(Big O)

1. 빅 오 기호

- 조건

* 시간적 복잡도를 데이터 크기 N의 함수로 표시하되 계수를 무시

 * 단, N이 무한대로 갈 때를 기준으로 평가

 * 입력 데이터가 최악일 때 알고리즘이 보이는 효율을 기준

 

- 수작학 정의

 * 임의의 상수 N0와 c가 있어서 N≥N0인 N에 대해서

   c · f(N) ≥ g(N)이 성립하면 g(N) = O(f(N))

 

- 빅 오의 예

 * g(N) = 2N + 5라면 이 알고리즘은 O(N)이다.

 * N > 1000이라면 40 · f(N) ≥ g(N)이 항상 성립

   N = 1000이라면 40 · f(N) = 40 · N = 40000이고,

   g(N) = 2 · 1000 + 5 = 2005에 불과하기 때문

   이 경우 N0는 1000으로 c는 40임. 이러한 값들은 임의로 할당 가능함

  예1) 210N² + 90N + 200 = O(N²)

  예2) 10N³ + 40N + 90N + 200 = O(N³)

  예3) 5N +15 = O(N)

 

- 빅 오의 계산법

 * 주어진 함수의 가장 높은 차수의 항만 끄집어내되 계수를 1로 하며 됨

 

- 포괄적 정의

 * 5N +15 = O(N²) = O(N³) = O(N⁴) = O(2ⁿ)

 * 실행 시간의 상한을 표시

 * "길어야 N 시간이면 된다."라는 의미

 

- 한정적 정의

 * 알고리즘의 특성을 표현하는 데는 가장 가까운 상한을 사용

 * 5N + 12는 O(N)이 가장 가까운 표현이라 할 수 있음