C - 자료구조 성능과 점근적 분석법

성능의 세가지 측면

최선의 경우 -> 빠르면 1 초 내에 번호를 찾아줌
평균의 경우 -> 평균 10초 이내에 번호를 찾아줌
최악의 경우 -> 아무리 늦어도 1분 이내에 번호를 찾아줌

성능을 이야기 할때는 최악의 경우를 상정하고 얘기해야한다.
**최악의 경우의 성능 = 보장 !!

자원의 두가지 측면 : 공간과 시간
	공간에 관련된 성능
    	- 공간 복잡도 : 특정한 프로그램을 수행하는데 요구되는 메모리 -> Memory
    시간에 관련된 성능
    	- 시간 복잡도 : 특정한 프로그램을 수행하는데 요구되는 시간 -> CPU
    * 시간이 공간보다 더 소중한 자원이다 !
    
공간 복잡도 및 시간 복잡도의 예
	- n개의 정수를 입력 받아서 합을 구하는 프로그램
    1. 정수를 하나씩 읽어서 합을 구함
    int i, x, sum;
	for (i = 0, sum = 0; i < n; i++) {
		cin >> x;
		sum += x;
	}
	cout << sum;
    //공간 복잡도 O(1): 요구되는 변수의 개수는 3개로 일정 n의 크기에 관계없이 일정한 공간만을 요구함
    //시간 복잡도 O(n): 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;
    //공간 복잡도 O(n): n의 크기에 비례해서 공간을 요구함
    //시간 복잡도 O(n): n의 크기에 비례해서 시간이 걸림
    
    ** 공간 복잡도 보다 시간 복잡도가 더 중요한 요소로 작용
    
    성능은 입력의 크기에 따라 결정됨
   - n : 입력의 크기
   - 시간 복잡도를 n의 함수로 표현하면 -> f(n)
   / -> 입력이 증가하면 시간도 증가(일반적)
   ㅡ -> 입력이 증가해도 시간은 일정(최고)
   \ -> 입력이 증가해도 시간은 감소(없음)
   - (입력의 크기, 계산시간) -> (n, f(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)임
- f(n) < =g(n)

g(n) = n^2
	- f(n)은 어떤 경우에도 n^2보다는 빠르다
    - f(n)의 최악의 경우는 n^2이다
    - f(n)의 상한은 n^2이다
   
**성능을 표현할 때 표준함수를 사용 -> n, n^2, 2^n, log n 등..
**Big-O표기법 : (1)+(2)+(3)+(4)+(5)