[TIL 240820] 자료구조와 알고리즘 #2

<시간복잡도, 공간복잡도, BIG-O 표기법>

1. 공간복잡도 (Space Complexity) : 알고르짐에 사용되는 메모리의 총량
2. 시간복잡도 (Time Complexity) : 알고리즘에 수행되는 연산 횟수 총량 (** 훨씬 더 많이 사용되는 개념)

요즘은 하드웨어의 성능이 좋아져서 공간복잡도보다 시간복잡도에 대한 내용이 더 중요하게 생각 된다.

int get_sum(int arr[], int n) {
	int sum = 0; 
    int i = 0;
    for(i = 0 ; i <n ; ++i) {
    	sum += arr[i];
    }
}

위와 같은 get_sum(a,b)의 경우

• 공간복잡도: n + 3
  - n의 의미: 배열에 담기는 개수
  • 3의 의미: 사용된 변수 (sum, i, n)
• 시간복잡도: n
  - for문이 반복되는 횟수로 시간복잡도를 계산한다

int get_sum(int n) {
	int sum = 0; 
    int i = 0; 
    int j = 0; 
    
    for(i = 1; i <=n; ++i) {
    	for(j = 1; j <=i ; ++j) {
        	sum += j; 
        }
    }
}

위와 같은 getsum(n)의 경우 시간복잡도를 계산하는 방법

즉 반복되는 횟수는 1 + 2 + 3 + ... + n 까지의 합을 구하는 것과 같다
따라서 위 get_sum(n)의 시간복잡도는
n(n+1)/2 가 된다.

• BIG-O 표기법
  - 시간복잡도와 공간복잡도의 최고차항만을 표기하여 간략하게 나타내는 표기법으로 보통 알고리즘을 수행하는데 걸리는 표준시간 대신 최악의 시간을 산출하여 표기한다