Time Complexity

1. 시간 복잡도

- 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화한 것으로, 알고리즘의 성능을 설명한다. 실행 시간이 아닌 연산 수치로 판별하는 이유는, 명령어의 실행 시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수 만을 고려하는 것이다.

- 알고리즘 문제를 풀기 전에 먼저 생각한 방법의 시간 복잡도를 계산해보고, 시간 안에 수행될 것 같은 경우에만 구현하는 것이 좋다.

- 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초 정도이다.

1초가 걸리는 입력의 크기

 

1.1 시간 복잡도 계산

- 상수는 버린다.

- 항이 두 개 이상일 때, 변수가 같으면 큰 것만 빼고 다 버린다.

- 항이 두 개 이상일 때, 변수가 다르면 그대로 놔둔다.

 

1.2 Big-O 표기법

- 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.

- Big-O로 측정되는 복잡성에는 시간복잡도와 공간복잡도가 존재한다. 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타내고, 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다. 최근에는 데이터를 저장할 수 있는 메모리가 발전하여 공간복잡도의 중요도가 낮아졌다.

Big-O Complexity Chart

 

참고

- https://blog.chulgil.me/algorithm/

- https://www.bigocheatsheet.com/

- 『알고리즘 기초 1/2』