[알고리즘 마스터] #0. 복잡도 (feate.시간복잡도, 공간복잡도)

 

복잡도에는 시간복잡도와 공간복잡도가 있다.

 

1. 시간 복잡도

1-1. 시간 복잡도

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

내가 쓴 코드가 얼마나 오랜 시간 걸리는 지를 나타내는지에 쓰인다.
이는 빅오 표기법이라는 것을 통해 나타낸다.

 

1-2.빅오(Big-O) 표기법

입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타낸 것.

for(int i=0; i<5; i++){
	for (int j=0; j<n; j++){
		for (int k=0; j<n; k++){
        
        cout << 'hi' << '\n';
        
        }
    }
}

for(int i=0; i<n; i++){   
        cout << 'hi' << '\n';
}

이 경우에 'hi'는 n에 따라 몇 번 반복이 될까?
정답은 5n^2 + n 이다.
이를 빅오 표기법으로 표현하면 O(n^2)가 된다.
가장 많이 영향을 끼치는 항의 상수 인자를 뺀 항만 넣어 표현한다.

 

1-3. 자료구조의 시간 복잡도 표

 

1-4. 시간 복잡도의 존재 이유

: 효율적인 코드로 개선하는 데에 쓰이는 척도가 되기 때문이다.

---

2. 공간 복잡도

2-1. 공간 복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
(정적 변수로 선언된 것 이외에 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우에도 포함)

int a[1004];

-> a배열은 1004x4바이트의 크기를 가지게 된다. 이 크기가 모두 컴퓨터의 공간을 차지하게 된다.

 

 

출처
면접을 위한 CS 전공지식 노트
https://velog.io/@gillog