algorithm (알고리즘)

어떠한 문제를 해결하기 위한 효율적인 절차

​

알고리즘의 성능분석

a. 계산복잡도 (시간 복잡도와 공간 복잡도로 구분)

- 알고리즘 수행에 걸리는 시간과 알고리즘 수행에 필요한 메모리가 얼마인지를 나타낸다.

- 현재는 플랫폼의 성능이 좋아져서 시간복잡도를 우선시한다.

(대부분의 프로그램 환경에서 공간에 대한 비용보다 시간에 대한 비용이 더 많이 들기 때문)

(메모리가 중요한 특정 환경에서는 공간복잡도가 우선이라고 한다.)

b. 시간 복잡도

- 입력 값에 따라 알고리즘의 수행에 걸리는 시간을 말한다.

- 단순히 시간으로 계산하면 테스트 환경에 따라 성능이 달라질 수 있기 때문에 입력 값에 따른 연산의 수행 횟수를 뜻한다.

- 지정문, 조건문, 반복문에 대하여 수행 횟수를 계산하면 된다.

(지정문 : 특정 변수에 값을 대입하는 명령, i=0; j=i+1; 처럼)

c. 공간 복잡도

- 알고리즘을 수행하는데 필요한 기억공간의 양을 문제의 크기에 대한 함수로 표현한 것이다.

- 과거에는 램의 용량이 크지 않았기 때문에 효율적이었지만 현재는 램 자체의 용량이 커진 덕에 중요도가 시간복잡도에 비해 낮아졌다.

공간 복잡도 예시

float Sum (float array[], int n)

{

float value = 0;

for(int i=0; i<n;++i)

value += array[i];

return value;

}

위 함수의 공간복잡도는 매개변수 array[]의 정확한 크기를 알 수 없으니

배열요소 n개 + value 변수의 공간 1개이다.

​

시간복잡도 함수

- 시간복잡도를 나타내는 표현

(입력 값에 따라 연산을 수행하는 횟수가 어떻게 계산되는지를 정의하는 것)

시간복잡도 함수 예시)

연산 빈도수 : 2 + n * 3 = (3n + 2)

​

점근표기법

- 근사치를 찾아내어 오직 단항으로만 식을 표현한다.

- 시간복잡도 함수는 일반적으로 (2+n*3)과 같이 다항식으로 표현되는 경우가 많은데 이는 값을 측정하는데 어려움을 준다.

(A 알고리즘과 B 알고리즘의 성능을 비교해야하는데 다항식으면 비교하기 어렵다)

- 시간복잡도를 계산할 때 정확한 단계의 계산은 무의미하다. 그래서 근사치를 찾고 최악 또는 평균 속도를 찾아내어 측정을 한다.

​

점근표기법의 분류

a. 빅-오 표기법(Big-Oh notation)

- 가장 많이 사용되는 표기법이라고 할 수 있다.

- 모든 N >= N0에 대해서 f(N) <= cg(N)이 성립하는 양의 상수 c와 N0이 존재하면, f(N) = O(g(N))이다. (위 정의를 굳이 이해할 필요는 없다. 이해하면 좋지만..)

- 알고리즘에서 시간의 복잡도를 표시하기 위해 대문자 오(O)를 사용하여 나타내는 표기법이다.

- 시간복잡도에서 가장 영향을 많이 주는 n에 대한 항만을 표시하는 방법이며 최악의 시나리오를 가정하는 방식이다.

- 최고차항의 차수만을 남기고 낮은 차수의 항들과 상수항, 최고차항의 계수는 제거한다.

(최고차항의 차수 외 나머지 차수의 값들은 연산 속도에 큰 영향을 미치지 않기 때문에 제거)

빅-오 표기법의 예)

시간복잡도 함수 :(3n + 2)

빅-오 표기 과정 : (3n + 2) -> 최고차항만 선택 : (3n) -> 계수 3을 제거 : (n) -> 빅오를 표현하는 O와 (n)을 조합 = O(n)

('빅-오 오브 엔'이라고 읽는다. 괄호()를 오브(of)로 읽는다.)

b. 빅-오메가표기법(Big-Omega)

- 최선의 경우에서의 시간 복잡도를 가정하는 방식이다.

- 모든 N, N >= N0에 대해 F(N) >= cg(N)인 조건을 만족하는 두 양의 상수 c와 N0가 존재하기만 하면 f(N)=Ω(g(N))이다. (빅오 수식에서 f(N)과 cg(N)에 부등호 방향이 반대)

c. 세타 표기법(Theta)

- 평균의 경우에서의 시간 복잡도를 가정하는 방식이다.

- g(N)이 O(g(N))과 Ω(g(N))을 동시에 만족하는 경우

 

 

참고출처

점근 표기법

 

자료구조 빅오표기법 수행시간

 

[자료구조] 시간 복잡도와 공간 복잡도

 

시간복잡도, 공간복잡도, 빅오표현법

 

다람쥐와 포동포동이

RememberCook 9월 28일 정식 출시!