면접을 위한 CS 전공지식 노트 [CHAPTER 5] (1)

[CHAPTER 5]. 자료 구조 

 

 

[SECTION 5.1] - 복잡도

 

5.1.1 시간 복잡도 

- 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 

- 시간복잡도와 공간복잡도는 알고리즘을 평가할 때 사용된다.

- 알고리즘은 여러 개인 경우가 많기 때문에 실행시간은 짧고, 공간은 적게 차지하는 더 효율적인 알고리즘이 어떤 것인지를 판단해야 한다.

 

 

빅오 표기법

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

쉽게 말해서 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는 데 쓰인다. 

 

👉🏻 ~ 이걸 보통 빅오 표기법으로 나타낸다!

 

 

빅오 표기법이란?

- 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다. 

- 시간복잡도 표기법은 빅오메가,빅세타,빅오 이렇게 3가지가 있다.

 

1. BigΩ (Best case)

- 빅오메가 표기법은 최선의 실행시간 즉, 가장 빠른 케이스를 나타내는 것이다.

 

 

 

2. Big𝚯 (Average case)

- 빅세타 표기법은 최선과 최악의 평균 실행시간 즉, 평균적인 케이스를 나타내는 것입니다.

 

 

3. BigO (Worst case)

- 빅오 표기법은 최악의 실행시간 즉, 가장 느린 케이스를 나타내는 것이다.

- 보통의 경우(프로그램 상에서 문제가 생겼을 때 느리게 실행되는 경우) 시간복잡도를 표기할 때 빅오 표기법을 사용한다. 

---

시간 복잡도의 존재 이유

- 효율적인 코드로 개선하는 데 쓰이는 척도가 된다. 

 

 

 

시간 복잡도의 속도 비교

- 빅오 표기법으로 시간복잡도 수행시간이 낮은 것부터 ~ 높은 것까지 알아보자.

출처:http://bigocheatsheet.com/

 

 

1. O(1)

- n이 몇 개 있든지 간에 실행시간이 일정한 것을 의미한다.

 

 

2. O(logn)

- logn은 log₂n과 동일하다.

- logn은 n을 절반으로 나눌 수 있는 수

 

3. O(n)

- 보통 n개의 모든 수를 탐색해서 찾아야 하는 수행시간을 의미한다.

 

 

4. O(nlogn)

- 병합 정렬을 통해서 값을 정렬할 때

 

 

5. O(n^2)

- 보통 이중 for문을 이용해서 n개의 값을 n번 대입해야 하는 수행시간을 의미한다.

 

 

6. O(2^n)

- 2의 n제곱만큼 늘어나므로 n이 늘수록 정말 가파른 수행시간을 가지는 것을 의미한다.

 

 

7. O(n!)

- 최악의 수행시간을 가지는 것을 의미한다.

---

5.1.2 공간 복잡도 

공간 복잡도란?

- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다. 

- 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함이다. 

- 공간 복잡도 역시 시간 복잡도처럼 보통 최악의 경우 (worst case)를 따져 빅오 노테이션으로 그 복잡도를 판단하게 된다.

- 공간 복잡도는 시간 복잡도 보다 중요하게 생각되지 않은 경우가 많으나 알고리즘 작성 시, 공간 복잡도를 아예 생각하지 않으면 위험할 수 있다. 따라서 공간 복잡도도 신경 써서 작성해 주자.

---

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

- 자료 구조를 쓸 때는 이러한 시간 복잡도를 잘 생각해야 한다.

- 보통 시간 복잡도를 생각할 때 평균과 최악의 시간 복잡도를 고려하면서 쓴다.

자료 구조의 평균 시간 복잡도

 

 

자료 구조 최악의 시간 복잡도

 

 

 

 

 

 

 

참고

https://velog.io/@sisofiy626/CS-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84%EC%99%80-%EA%B3%B5%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84

https://fomaios.tistory.com/entry/Algorithm-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity%EB%9E%80

https://velog.io/@kkookk55/CS%EC%A7%80%EC%8B%9D-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84%EC%99%80-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84