[코드잇] 시간복잡도, 공간복잡도 이해하기(Feat. 연속출석)

기본 자료 구조들 - 알고리즘 · 자료구조 강의 | 코드잇

학교 전공수업을 자료구조개론을 듣고있는 터라 코드잇으로 '기본자료 구조들' 수업을 틈틈히 같이 듣고 있다.

자료구조 수업을 듣다 보면, 특히나 "시간복잡도" 라는 단어가 많이 나온다.

자료구조, 알고리즘의 비교를 위해선 무조건 알아야 하는것이 시간복잡도와 공간복잡도 이다.

 

 

 

 

시간복잡도 -> 해당 코드가 시간이 얼마나 걸리는지?

• +,-,*,/ 등의 기본 연산은 하나의 스텝으로 생각한다. 
• +=, *=, (a+b*c) 등의 혼합 연산도 하나의 스텝으로 생각해도 된다.(이후 설명_

Example 1.

 +, +, * , + 4개의 연산자로 4step이다.

 

T(n) = 4

 

Example 2.

첫번째 for 문에 rows 만큼 i++

첫번째 for 문에 cols 만큼 j++

그 안에 + 하나

 

전체 step은 rows * cols 만큼 반복된다.

T(n) = n^2

 

 

 

• (10n + 10)  vs

10n + 10	vs	0.01n^2 + 10
2000n + 3	vs	nlogn + 1000
n^3	vs	10n^2 + 100000n

각 시간복잡도 함수를 비교해볼때, 그래프로 생각해보면

어차피 최종 차수가 높은 녀석이 끝까지 가면 다 이긴다는 것을 알 수 있다. 그래서 나온 규칙이

• 상수는 다 무시하기
• 가장 큰 차수 항만 비교하기

이것을 보다 더 편하게 표기하기 위해, 점근 표기법(Asymptotic notation)을 사용한다.

점근 표기법엔 크게 세가지가 있는데,

• Big - O - notation O(f(n))
• Big - Ω - notation Ω(f(n))
• Big - Θ - notation Θ(f(n))

여기서 Big - O - notation 은 시간복잡도 함수의 upper bound 로써, 아무리 worst case로 진행되어도 저 이상은 넘지않는다 는 느낌이 있다.

여기서 Big - Ω - notation 은 시간복잡도 함수의 lower bound 로써, 아무리 best case로 진행되어도 저 이상 아래로 가지 않는다 는 느낌이 있다.

여기서 Big - Θ - notation 은 둘의 사이 이다.

 

여기서 Big - O -notation이 가장 많이 쓰인다.

대략적인 증가추세는 다음과 같다.

 

 

 

 

 

 

공간복잡도 -> 해당 코드가 메모리를 얼마나 사용하나

 

Example 1.

a, b, c의 세 변수에 해당하는 메모리 할당이 필요함.

T(n) = 3

O(1)

 

Example 2.

 

포인터의 동적할당.

n개의 메모리가 필요함.

 

 

 

 

 

그런데 요즘은 컴퓨터들이 메모리가 정말 충분해서 공간복잡도는 잘 안따지고, 위에 설명한 시간 복잡도를 주로 따진다고 한다.

 

 

 

 

 

 

 

어느새 이번주 5일연속 공부중! 그리고 4주 연속 출석중 ㅎㅎ

매일 출석하는 것을 강하게 알려주고 또 통계도 볼 수 있으니 더 뿌듯해서 자주 오고 싶어진다.

습관을 잡기에 참 좋은 코드잇!