자료구조 2주차 성능 분석

성능

성능이란 무엇인가?

정답을 빠른 시간 내에 출력: 요구하는 자원이 최소 -> 성능, 효율이 좋다

performance (efficiency) = 결과/비용

• 성능 또는 효율: 일을 잘 한다 + 소요된 시간 (자원)이 적다

 

성능의 세가지 측면

1. 최선의 경우 : 빠르면 1초 내에 검색
2. 평균의 경우: 평균 10초 내에 검색
3. 최악의 경우: 아무리 늦어도 1분 이내에 검색

-> 최선, 평균의 경우는 과장광고.. 최악의 경우로 말해야 사용자의 만족도에 도움이 됨

최악의 경우를 보장하는 것

 

 

자원의 두 가지 측면: 공간과 시간

공간 복잡도 space-complexity

• 공간에 관련된 성능
• 특정 프로그램을 수행하는 데 요구되는 메모리
• memory

시간 복잡도 time-complexity

• 시간에 관련된 성능
• 특정 프로그램을 수행하는 데 요구되는 시간
• cpu

시간이 공간보다 소중한 자원이다.

cpu가 더 비쌈

 

 

 

예) n 개의정수를입력받아서합을구하는프로그램

1. 정수를 하나씩 읽어서 합을 구함

int i, x, sum;
    for ( i = 0, sum = 0; i < n; i++ ) {
        cin >> x;
        sum += x;
    }
cout << sum;

 

- 공간 복잡도 O(1)

n의 크기에 관계없이 일정한 공간만을 요구함

변수 3개의 공간만 쓰면 됨, n번 실행함

 

- 시간 복잡도 O(n)

n의 크기에 비례해서 시간이 걸림

for문 n번 루프

 

 

2. 정수를 하나씩 읽어서 저장한 후에 합을 구함

int i, *x, sum;
x = new int[n];
for ( i = 0; i < n; i++ )
    cin >> x[i];
for ( i = 0, sum = 0; i < n; i++ )
    sum += x[i];
cout << sum;

int i, *x, sum;
x = new int[n];                          // O(1) - 메모리 할당 (크기는 n이지만 상수 시간에 이루어짐)
for ( i = 0; i < n; i++ ) cin >> x[i];  // O(n) - 입력을 n번 받음
for ( i = 0, sum = 0; i < n; i++ )      // O(n) - n개의 요소를 더함
    sum += x[i];
cout << sum;                            // O(1) - 출력 한 번

 

- 공간 복잡도 O(n)

n의 크기에 비례해서 공간을 요구함

n개의 저장공간 요구

 

- 시간 복잡도 O(n)

n의 크기에 비례해서 시간이 걸림

for문 n번 루프 두번

O(n)+O(n)=O(n)

 

점근적 분석법

(asymptotic complexity)

성능은 입력의 크기에 따라 결정됨

n:입력의 크기

시간복잡도를 n의 함수로 표현 -> f(n)

성능 그래프: (n,f(n))

1) 입력이 증가하면 시간도 증가 (일반적)

2) 입력이 증가해도 시간은 일정 (이상적)

3) 입력이 증가하면 시간이 감소 (있을수없음)

시간 복잡도는 매우 큰 입력 (reasonably large length of input) 에 대해서 측정함

n이 매우 큰 경우에 대해서만 의미 잇는 성능이 측정됨

g(n)을 이용한 f(n)의 성능 표현

동일한 크기의 입력을 처리할 때, g(n)은 f(n)보다 더 많은 시간을 요구함

= g(n)은 f(n)보다 성능이 나쁨

= g(n)은 f(n)의 최악의 경우

f(n)의 상한은 g(n)

f(n) ≤ g(n)

• g(n)은 f(n)의 성능을 나타내는 척도로 사용됨
• 많이 사용되는 표준적인 함수 (1, n, log n, n², n log n, nⁿ) 이용

요약

(1) 최악의 경우의 성능 -> 보장
(2) 공간 복잡도보다 시간 복잡도가 더 중요
(3) (입력의 크기, 계산 시간) -> (n, f(n))
(4) 점근적 분석법 -> 매우 큰 입력을 가정
(5) 표준 함수를 사용 ->1, n, n², 2n, log n
(6) Big-O표기법: (1)+(2)+(3)+(4)+(5)

big-O 표기법

 

g(n)은 f(n)의 최악의 경우

 

빅오 표기법의 정의

f(n) is O( g(n)) as n->∞

1. f(n) ≤ g(n)
2. f(n) ≤ g(n) for  n₀ <n      -> 항상 n₀보다 큰 n에 대해서만 요구하겠다
3. f(n) ≤ M g(n) for  n₀ <n  -> 동일한 비율로 증가하는 함수를 허용하기 위해서 상수 M을 인정함

 

3번 : g(n)이 5n이든 10n이든 f(n)=n에 비례함

 

 

 

성질 1

어떤 n > n₀ 에 대해서 g₁(n) < g₂(n) 이라면 f(n) = O( g₁(n) )은 f(n) = O( g₂(n) )을 의미한다.

 

예) f(n) = O(n)라면 f(n) = O(n²)이다.

 

증명)

f(n) ≤ M g₁(n) --- (정의 1)

g₁(n) < g₂(n)

 

-> f(n) ≤ M g₁(n) ≤ M g₂(n)

 

-> f(n) ≤ M g₂(n)

 

 

 

 

성질 2

어떤 상수 k에 대해서  f(n) = O( k g(n) )이라면, f(n) = O( g(n) )이다.

 

예) f(n) = O( 5n² )라면 f(n) = O( n² )이다.

 

 

 

 

성질 3

f(n) = O( g₁(n)+ g₂(n) ) 이고 어떤 n > n₀ 에 대해서  g₁(n) < g₂(n) 이라면 f(n) = O( g₂(n) )이다.

 

예) f(n) = O( n²+n )이라면 f(n) = O( n² )이다.