[k-mooc/자료구조] 02. 성능 분석

02-1. 성능과 점근적 분석법

성능(Performance)

성능(Performance/Efficiency) = 결과(Solution) / 자원(Resource)

동일한 결과라도 소요된 자원에 따라 효율에서 차이가 발생하게 된다.

 

자원	복잡도	의미	장치
시간	시간복잡도 (time-complexity)	수행 시간	CPU
공간	공간복잡도 (space-complexity)	메모리 사용량	메모리

실제 성능 논의에서는 공간보다 시간이 더 중요하다. (CPU가 더 비싸고 늘리기 어려움 ⇒ 성능에 보다 직접 영향)

성능 측정 기준

경우	설명
최선	빠를 때 기준	과장: 1000번 테스트 하면 딱 1번
평균	보통의 상황 평균값	과장: 반반 확률
최악	절대 보장되는 최악 기준	보장: 사용자가 어떤 경우라도 기대한 시간보다 빠르므로 만족할 수 있음

성능을 이야기할 때는 항상 최악의 경우를 선택한다.

 

시간복잡도와 공간복잡도

공간복잡도보다 시간복잡도가 성능에 있어서 더 중요한 요소(factor)로 작용한다.

int sum = 0;
int x; //사용자 입력 

for(int i=0; i<n; i++) { //n번 수행 
	x = Integer.parseInt(br.readLine()); 
  sum += x;
}

System.out.println(sum);

/*
* 공간 복잡도: 변수 3개 O(1) - n의 크기에 관계없이 일정한 공간만 요구
* 시간 복잡도: O(n) - n의 크기에 비례해서 시간 소요
*/

정수를 하나씩 읽어서 합 구하기

int sum = 0;
int[] x = new int[n]; //n개 배열 - 사용자 입력 

for(int i=0; i<n; i++) { //n번 수행 
	x[i] = Integer.parseInt(br.readLine()); //입력받은 숫자를 배열에 저장
  sum += x[i];
}

System.out.println(sum);

/*
* 공간 복잡도: 변수 n개 O(n) - n의 크기에 비례해서 공간 요구
* 시간 복잡도: O(n) - n의 크기에 비례해서 시간 소요
*/

정수를 하나씩 읽어서 저장한 후에 합 구하기

 

시간복잡도 표현

성능은 입력의 크기(n)에 따라 결정된다. ⇒ 수행 시간 f(n) ⇒ 그래프 (n, f(n))

 

f(n)의 종류

1. 입력이 증가하면 시간도 증가 - 일반적
2. 입력이 증가해도 시간이 일정 - 이상적
3. 입력이 증가해도 시간이 감소 - 불가능

1번이 가장 일반적인 경우고 2번을 추구하게 된다. 

 

점근적 분석법(Asymptotic Analysis)

시간복잡도는 입력(n)이 작은 경우는 무시하고 입력이 매우 클 때 성능을 분석하게 된다.

https://www.umsl.edu/~siegelj/CS4740_5740/Complexity/AComplexity.html

 

f(n)이라고 하는 성능을 g(n)이라고 하는 함수로 표현할 수 있다.

이 때 g(n)은 f(n)의 최선/평균/최악 중 ‘보장’되는 최악의 경우를 표현하므로, 항상 f(n)보다 위에 있다.

(언제나 f(n)의 최악의 경우만을 표현하므로 모든 경우를 포함하는 f(n)보다 항상 시간이 오래 걸린다)

 

정리하면:

g(n)을 이용한 f(n)의 성능 표현
1. g(n)은 f(n)보다 성능이 나쁘다.
2. g(n)은 f(n)의 최악의 경우다.
3. f(n)의 상한(upper bound)은 g(n)이다.

f(n) ≤ g(n)

 

이처럼 g(n)은 f(n)의 성능을 나타내는 척도로 사용된다.

그래서 g(n)은 많이 사용되는 표준적인 함수를 사용한다: 1, N, logN, N^2, NlogN, N^n

 

 

02-2. Big-O 표기법

세 가지 조건

1. f(n) ≤ g(n)
2. f(n) ≤ g(n) for n_0 < n
   점근적 분석법에서는 작은 값을 고려하지 않기로 했기 때문에 n_0 아래로는 고려하지 않음
3. f(n) ≤ Mg(n) for n_0 < n
   동일한 비율로 증가하는 함수를 허용하기 위해 상수 M을 인정
   f(n)은 Mg(n)보다 작기만 하면 된다 (빅오표기법에서 가장 중요)

 

중요한 성질

• 부가 설명
  • 어떤 n>n_0 에 대해서: 점근적 분석에선 작은 값은 무시하고 무한히 큰 n 에서의 경향만 고려한다.
  • g₁(n) < g₂(n) 이라면: 시간복잡도 기준 g₂(n)이 g₁(n)이 더 많은 시간을 요구하는 함수이다.
    - 예를 들어 g₁(n) = n, g₂(n)=n^2일 때 n이 클수록 g₂는 훨씬 더 빠르게 커진다.
  • f(n) = O(g₁(n))이면 f(n)=O(g₂(n)): 만약 f(n) ≤ M * g₁(n)이 성립한다면, 이미 g₁(n) < g₂(n)인 상태니까 M * g₁(n) < M * g₂(n)도 성립하게 된다.
    즉, 더 느린 함수로 빅오를 써도 항상 맞긴 맞다. ⇒ 작은 빅오는 큰 빅오에 포함된다.
    f(n) = O(n) 이라 해도 사실 O(n²), O(n³) 도 다 맞다고 쓸 수 있다.
  • 따라서 f(n) ≤ M * g₁(n) < M * g₂(n)이 되니까 결론적으로 f(n) = O(g₂(n))라고 할 수 있다.
  • g(n)은 f(n)의 최악의 경우이다.

 

 

02-3. Big-O 표기법의 예

https://blog.stackademic.com/how-to-calculate-big-o-notation-time-complexity-5504bed8d292

시간복잡도	특징	예
O(1)	가장 빠름	한 번만 실행
O(logN)	매우 빠름	이진 탐색 등
O(N)	선형 증가	배열 순회
O(NlogN)	비교적 빠름	정렬 알고리즘 등
O(N²)	느림, 중첩루프	버블 정렬 등
O(2ⁿ)	매우 느림	재귀 피보나치