Time Complexity 들어가기 전 Complexity Analysis 부터 해보겠다.

Complexity Analysis

Complexity Analysis(복잡도 분석)이란?

알고리즘을 푸는데 있어서 시간과 공간이 얼마나 차지하는지를 나타내는 지표

Complexity Analysis의 중요성

코드의 효율성을 이해하고 개선하는데 도움을 준다.

Complexity Analysis의 기준은?

알고리즘이 소모하는 소요 시간(시간복잡도)과 메모리사용량(공간 복잡도)

그래서 Big-O 표기법을 사용한다.

Big-O 표기법이란?

알고리즘의 효율성을 표기해주는 표기법

효율성 좋은 순서 : O(1) < O(log n) < O(n) < O(N log n) < O(n2) < O(n3) < O(2n) < O(n!)

Big-O 분류

Data Structure complexity Big-O 표기법 정리

Time Complexity(시간 복잡도)

알고리즘의 수행시간 분석결과

1. Big-O 표기법 사용한다.
2. 데이터의 크기가 같더라도 실제 데이터에 따라 시간복잡도가 달라질 수 있다.
3. 특별한 언급이 없다면 복잡도는 시간복잡도를 나타낸다.

Space complexity(공간 복잡도)

알고리즘의 메모리 사용량에 대한 분석결과

역시 Big-O 표기법 사용한다.