알고리즘 분석 방법 - 시간 복잡도, 빅오 표기법

1. 효율적인 알고리즘

- 알고리즘이 시작하여 결과가 나올 때까지의 수행 시간이 짧으면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘이다. 일반적으로 수행시간이 메모리 공간보다도 더 중요하게 고려됨

2. 수행 시간 측정 방법

1) 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터 상에서 실행 시켜 수행시간 측정

- 알고리즘을 구현하고 테스트 하는 것이 필요

- 똑같은 하드웨어를 사용해서 알고리즘 수행 시간을 측정해야 함

- 소프트웨어 환경 또한 중요 (예: 프로그래밍 언어에 따라 수행 속도가 달라질 수 있다. 언어 번역 방식 차이에 따라..)

- 실험되지 않은 입력에 대해서는 수행 시간이 합당하다고 볼 수 없다.

2) 알고리즘 복잡도 분석

- 실제 알고리즘을 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법, 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

3. 알고리즘 분석

- 시간 복잡도와 공간 복잡도 측면을 고려할 수 있음

- 대개 알고리즘 복잡도라 하면 시간 복잡도를 의미함 (알고리즘이 차지 하는 공간 보다는 수행 시간에 더 중요)

1) 시간 복잡도: 알고리즘 수행 시간 분석

2) 공간 복잡도: 알고리즘이 사용하는 기억공간 분석

4. 시간 복잡도

- 알고리즘의 절대적인 수행 시간을 나타내는 것이 아님, 

- 어떤 알고리즘이 수행하는 연산(산술연산, 대입연산, 비교연산, 이동 연산)의 개수를 계산하여 알고리즘을 비교할 수 있다. 

5. 시간 복잡도 함수

- 연산들의 수행횟수는 고정된 숫자가 아님, 보통 프로그램에 주어지는 입력의 개수 n에 따라 변하게 됨

- 연산의 수를 입력의 개수 n의 함수로 나타낸 것, T(n)으로 표기함

예시) 양의 정수 n을 n번 더하는 문제

1) 알고리즘 종류

알고리즘  A	알고리즘 B	알고리즘 C
sum <- n*n;	for i <- 1 to n do  sum <- sum + n;	for i <- 1 to n do    for j <- 1 to n do      sum <- sum + 1;

2) 알고리즘 비교

	알고리즘 A	알고리즘 B	알고리즘 C
대입연산	1	n	n*n
덧셈연산		n	n*n
곱셈연산	1
나눗셈연산
전체 연산 수	2	2n	2n^2

- 모든 연산이 동일한 시간이 걸리고 하나의 연산이 t만큼 시간이 걸린다고 가정, 루프 제어 연산 생략

- A는 2t에 비례하는 시간이 필요, B는 2nt의 시간, C는 2n^t만큼의 시간이 걸림

그러므로 n이 커질수록 알고리즘간의 차이가 커지게 됨.

연산의 개수를 이용하여 알고리즘들을 비교하고 비교한 결과를 바탕으로 가장 효율적인 알고리즘을 선택할 수 있다.

6. 빅오 표기법

- 입력 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도함

- n의 값에 따른 함수의 상한 값을 나타내는 방법

- 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시 하는 방법

(기본 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것, 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용)

* 주의 log n은 없애면 안된다.

- 많이 사용하는 빅오표기법 (순서대로 표기)