시간 복잡도

1 개요

time complexity

시간 복잡도

• 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
• 컴퓨터 과학에서는 알고리즘 수행을 위한 계산 복잡도로 볼 수 있음
• 통상 알고리즘의 기본 연산 수행 수로 판단
• 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용

2 빅-오(big O) 표기

• n 은 입력 사이즈

<img src=https://wikimedia.org/api/rest_v1/media/math/render/svg/328a10f1262414118d5f14b437b7b4ae4c2ac1a0> <img src=https://wikimedia.org/api/rest_v1/media/math/render/svg/497720dca0f6c8c6268f7a1332b993e597136e8b> <img src=https://wikimedia.org/api/rest_v1/media/math/render/svg/b3ac153dc1218e0479ba844225929249ed3057bf> <img src=https://wikimedia.org/api/rest_v1/media/math/render/svg/0789ffe69d9b6089a08167f1500221ebdba03ffc>

3 같이 보기

• 다항 시간
• 지수 시간
• 상수 시간
• 계산 복잡도
• 시간
• 복잡도

4 참고

• https://en.wikipedia.org/wiki/Time_complexity