[알고리즘] 알고리즘 성능 분석

알고리즘: 어떤 문제를 컴퓨터가 해결하는 방법
=> 주어진 문제를 해결하는 명료한 한 가지 방법을 써놓은 것(소스 코드 ≠ 알고리즘)
데이터구조: 데이터를 조직하고 접근하는 체계적 방식
 

[알고리즘 성능 측정 기준]

• 정확성 : 내가 원하는 출력이 나오는지?
• 작업량 : 알고리즘에서 처리해야하는 작업의 양이 얼마나 되는지?
• 메모리 사용량 : 알고리즘이 사용하는 메모리의 양이 많은지 적은지?
• 단순성 : 복잡한 알고리즘은 분석도 복잡하다
• 최적성 : 개선할 부분이 없는지?

[알고리즘 실행 시간 분석]

=> 물리적 측정 방법 : 스톱워치로 알고리즘의 성능을 분석할 수 있을까?
하나의 알고리즘을 좋은 CPU, 나쁜 CPU에서 각각 처리해봤을때 정확한 비교분석을 할 수 없다.
물리적 측정 방법 -> 알고리즘 성능 제대로 비교 X

=> 프로그램의 실행 시간이 알고리즘의 성능을 나타내줄 수 있을까? X
프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 많은 것들에 의해 변할 수 있음

=> 다양한 입력에 대한 실행 시간을 반영하지 못한다
항상 같은 속도로 동작하지 않는다. 입력의 크기나 특성에 따라 달라질 수 있다.

“알고리즘 수행시간은 하드웨어에 의존하지 않고도 정의될 수 있어야한다.”

“좋은” 알고리즘 설계 기준
1. 실행시간
2. 저장공간 사용량
=> 적은 공간 사용 = 적은 메모리 사용

[알고리즘 실행시간]

=> 최선실행시간, 평균실행시간, 최악실행시간
- 최악의 실행시간으로 분석!
- 알고리즘을 사용하는 어떤 경우에도 보장되는 성능 의미

알고리즘 수행 시간을 지배하는 것 => 반복문
반복문은 입력 크기가 클수록 더 많이 반복해야하기 때문에 실행시간이 늘어난다.
반복문의 수행 횟수를 입력의 크기에 대한 함수로 표현함

int main(){

	int N = 10, cnt = 0;
	for (int i = 0; i < N; i++)
		cnt++;
	printf("%d", cnt);

	return 0;
}

간단하게 N 값이 얼마인지 알아보는 코드를 구현해봤다.
이때 반복문은 주어진 N 값만큼 반복문을 돌아보기 때문에 이 반복문은 N번 실행된다.
따라서 수행 시간은 N

int main(){

	int N = 10, cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cnt++;
	}
	printf("%d", cnt);

	return 0;
}

이번 코드는 반복문 안에 반복문을 한번 더 실행시켜주었다.
이 코드는 항상 N²번 실행되게 된다.
따라서 수행 시간은 N²
 

[점근 표기법]

=> 알고리즘의 수행시간을 대략적으로 나타내는 방법
- 점근 표기법의 장점 : 성능 비교 용이

데이터의 크기가 작은경우 : 성능 공식의 모든 요소가 성능 차이를 나타냄
데이터의 크기가 큰 경우 : 최고차 항을 제외한 나머지 항의 영향이 거의 없음
 

대표적인 표기법 세가지

1. O 표기법 (Big O)
2. Big Omega 표기법
3. Big Theta 표기법

[O 표기법 (Big O)]

- 최악의 경우 알고리즘 수행 시간
- 표기 방법
고등학교 수학시간에 배운 극한을 떠올리면 편하다.
극한을 계산할때 n이 무한대로 가면 가장 영향이 큰 녀석이 차수가 가장 큰 항이다.
빅오 표기에서도 마찬가지로 2n² + 3n 성능의 알고리즘이 있을때, 가장 큰 영향을 주는 최고차항만 남겨두고 표기한다.
2n² + 3n 성능의 알고리즘 => O(n²)

O(n³)은 수행 시간이 n³을 넘지 않는 증가 함수의 집합이기 때문에 2n², 5n 도 O(n³) 이라고 쓸수 있다.

O 표기	알고리즘
O(1)	해시 테이블
O(log₂n)	이진 탐색
O(n)	순차 탐색
O(n logn)	병합 정렬, 퀵 정렬
O(n²)	버블 정렬, 삽입 정렬
O(n³)	행렬 곱셈

 

[Ω 표기법 (Big Omega)]

- 최선 알고리즘 수행 시간
- 꼭 수행해야만 하는 최소한의 수행 시간
- Big O와 반대로 수행시간이 더 큰 성능 공식을 집합으로 가진다.
 
Ω(n²)에는 2n², n³ 모두 포함 되어있다.
 

[Θ 표기법 (Big Theta)]

- O 표기법과 오메가 표기법을 모두 만족시키는 표기법이다.
- 자신과 수행시간이 같은 성능 공식들만 포함된다.
 
Θ(n²)에는 2n²+2, 1/3n² 들이 포함 되어있다.

---

컴퓨터 프로그래밍 전공하는 대학생이 공부했던 내용을 정리하기 위해 적는 소소한 블로그 입니다.
잘못된 내용은 댓글에 달아주시면 피드백 감사히 받겠습니다!

[참고한 도서]
- 데이터 구조 원리와 응용
- 이것이 자료구조 + 알고리즘이다
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략