0. 시간 복잡도 & 공간 복잡도

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링

---

◆  시간 복잡도 & 빅오 표기법

- 시간 복잡도란 '문제를 해결하는데 걸리는 시간과 입력의 함수 관계'

- 설계한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내느데 쓰이며, 보통 빅오 표기법으로 표시

       ex) 입력 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 10n2+n 이라고 하면, 아래와 같이 코드 구성 가능          (C++)

for (int i = 0; i < 10; i++) {
	for(int j = 0; j < n;j ++) {
    	for(int k = 0; k < n; k++) {
        	if(true)
            	cout << k << endl;
        }
    }
}

for(int i = 0; i < n; i++) {
	if(true)
    	cout << i << endl;
}

- 빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것인데, 앞서 말한 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O(n^2)

- 빅오 표기법을 표기할 때에는 계수나 상수는 생략하여 표시

   ex) O(2n) = O(n) , O(3n^2 +k ) = O(n^2)

(정답은 아니지만 필자는 보통 반복문이 중첩된 횟수를 k이라고 하면 O(n^k)로 생각하고 설계합니다)

- 알고리즘의 성능 분석에 사용되며, 효울적인 코드를 개선하는데 쓰이는 척도가 됨.

- 시간복잡도 그래프 (출처 : 나무위키)

Ref : https://namu.wiki/w/%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84

 

---

◆  공간 복잡도

- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양

- 일반적으로 공간이 하나가 생성되면 1이라고 표현

- 주로 빅오 표기법으로 표시

 ex ) int A = 1;              => 공간 복잡도 O(1)

 ex)  for(int i =0; i < 999; i++) {           => 공간 복잡도 O(1)

      ~~

}

- 아래와 같은 재귀함수는 1부터 n까지의 공간을 차지, O(n)으로 표기

int factorial(int n) {

     if(n == 1)
     	return 1;
        
    return n*factorial(n-1);

}

---

◆  자료구조에서의 시간 복잡도

 

Ref :&nbsp;https://www.bigocheatsheet.com/

---

 

 지나가다 한 번씩 봐서 그런건지 무언가 익숙했던 요약이었습니다.

 위의 글과 관련하여 추가적인 내용이나 피드백은 언제나 환영입니다 :)