알고리즘 시간 복잡도(Time Complexity)

프로그래머스나 백준에서 알고리즘 문제를 풀다보면 시간 초과를 경험하는 순간이 있습니다.
그러면 시간 초과는 왜 발생하고, 알고리즘에서 반복문을 최소화 해야 하는 이유에 대해 설명하겠습니다.
 
우선, 시간 복잡도라는 개념에 대해 알고 있어야합니다.
시간 복잡도란, '입력한 값에 따라 연산이 시작되었을 때 연산 횟수에 비해 시간이 얼만큼 소요되는지?'를 의미합니다.
 

Big-O 표기법

1. O(1)

- 입력값이 증가해도 시간은 일정하다.
- 반복문을 사용하지 않음.

2. O(n)

- 입력값의 증가에 따라 일정하게 시간이 증가한다.
- 1번의 반복문을 사용 (반복문의 반복 횟수만큼 시간이 증가한다.)

3. O(log n)

- 로그 복잡도라고 부른다.
- 한번 실행될 때, 그 다음 해답을 찾는 경우의 수를 절반씩 줄여나가는 방법으로 대표적인 예로는 이진 탐색 트리가 있다.
 

4. O(n2)

- 입력값이 증가함에 따라 시간이 n의 제곱의 비율 만큼 증가한다.
- 대표적인 예시로는 이중 for문이 있다.

5. O(√n)

- 대표적인 방법으로 "약수 찾기" 알고리즘을 예를 들 수 있다.

약수 찾기 예시

간략한 설명)
100의 약수를 구하는 로직으로 100번 로직을 돌면서 구하는 것이 아닌, 10번만 돌면서 100의 약수를 구하는 것이다.
 
* 출처
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/